[JAVA]문자열 뒤집기(Baekjoon)

문제

문제

영어 알파벳 대문자로만 구성된 문자열이 N개 있다 (S[1], S[2], ..., S[N] 이라 칭하자).

Reverse(T)는 임의의 문자열 T를 뒤집은 문자열 이라 하자 (명백히, 모든 문자열 T에 대해 Reverse(Reverse(T)) = T 이다).

가령 Reverse("ABC") = "CBA" 이다.

당신은 N개의 문자열 각각에 Reverse() 함수를 적용할지 말지 고를 수 있고, 이를 통해 문자열이 사전순으로 정렬되도록 하고 싶다 (문자열이 N개 이므로 2N 가지의 방법이 존재한다).

각 문자열에 Reverse() 함수를 적용한 경우를 '1' 적용하지 않은 경우를 '0'으로 나타내면, 길이가 N인 0-1문자열이 된다 - 이를 "리버스 문자열" 이라 하자. (리버스 문자열은 길이가 N인 0-1 문자열이다).

예를 들어 N = 3이고 S[1] = "ABC", S[2] = "XC", S[3] = "DZ" 라 하자.

• 리버스 문자열이 "000"인 경우: 세 문자열은 원래 문자열인 "ABC", "XC", "DZ" 가 되고 사전순으로 정렬되지 않은 상태이다 (S[3]이 S[2]보다 앞선다).
• 리버스 문자열이 "001"인 경우: 3번 문자열에만 Reverse() 함수를 적용하면 세 문자열은 "ABC", "XC", "ZD" 가 되어 사전순으로 정렬된다.
• 리버스 문자열이 "010"인 경우: 2번 문자열에만 Reverse() 함수를 적용하면 세 문자열은 "ABC", "CX", "DZ"가 되어 사전순으로 정렬된다.
• 리버스 문자열이 "101"인 경우: 1번과 3번 문자열에 Reverse() 함수를 적용하면 "CBA", "XC", "ZD"가 되어 사전순으로 정렬된다.
  이 외에도 다른 방법으로 세 문자열을 사전순으로 정렬할 수 있다.

입력으로 주어진 N개의 문자열을 사전순으로 정렬하는 리버스 문자열이 항상 존재한다는 가정하에, 그러한 리버스 문자열 중 사전순으로 가장 앞서는 리버스 문자열을 출력하시오.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

테스트 케이스의 첫 줄에 문자열의 수 N이 주어진다.

다음 N줄에 걸쳐 한 줄에 하나씩 영문 알파벳 대문자로만 구성된 문자열이 주어진다.

출력

각 테스트 케이스에 대해 조건을 만족하는 리버스 문자열 중 사전순으로 가장 앞서는 리버스 문자열을 출력한다.

제한

• 1 ≤ T ≤ 50
• 2 ≤ N ≤ 150
• 2 ≤ Length (S[i]) ≤ 20
• 임의의 i ≠ j 에 대하여 Reverse(S[i]) ≠ S[j] 와 S[i] ≠ S[j] 는 항상 성립한다.
• 입력으로 주어지는 모든 케이스에 대해, 주어진 문자열을 사전순으로 정렬하는 리버스 문자열은 항상 존재한다.

예제 입력 1

2
3
ABC
ABD
XY
3
ABC
XC
DZ

예제 출력 1

000
001

풀이

수도코드를 짜봤다. 백트래킹은 트리 구조의 플로우를 가지기에 트리를 그려 케이스를 도식화했다.

사전순으로 가장 빠른 리버스 문자열을 출력하면 되기에 forward를 먼저 진행, 그 다음 reverse를 진행하는 식으로 설계했다.

현재 깊이의 문자열과 이전 깊이의 문자열(직전 문자열)과 비교하여 사전순으로 올바르다면 다음 깊이로 함수를 재귀적으로 호출한다. 반환값이 참이면 해를 찾은 것이므로 true를 리턴한다.

반환값이 거짓이라면 현재 깊이의 문자열을 리버스하고, 위의 과정을 반복하여 진행한다. 이전 문자열과 비교하여 사전순으로 올바르다면 다음 깊이로 함수를 호출. 참이면 해를 찾은 것.

하지만, 여기서도 해를 찾지 못했다면 현재 문자열이 아닌 이전 문자열들에서 변화가 필요하다. 따라서, 현재 뒤집은 문자열을 다시 뒤집어 주고, 거짓을 리턴하는 베이스 케이스가 실행된다.

알고리즘 설계는 전혀 문제가 없는 것 같은데 오답처리가 된다. 이유를 하루종일 생각해봐도 찾지 못했다. 심지어 최신 문제라 풀이도 없어서 정답을 맞은 사람의 코드를 확인할 수가 없다.

 

import java.io.*;

public class _19597 {
    public static String[] arr;
    public static int[] reversed;
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int N = Integer.parseInt(br.readLine());
            arr = new String[N+1];
            arr[0] = "";
            reversed = new int[N+1];
            for(int i = 1; i <= N; i++)
                arr[i] = br.readLine();
            solve(1);
            for(int i = 1; i <= N; i++){
                sb.append(reversed[i]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
    public static boolean solve(int depth){
        // termination condition
        if(depth >= arr.length)
            return true;
        // case 0 (forward)
        if(arr[depth-1].compareTo(arr[depth]) < 0)
            if(solve(depth+1))
                return true;
        reverse(depth);
        // case 1 (reverse)
        if(arr[depth-1].compareTo(arr[depth]) < 0)
            if(solve(depth+1))
                return true;
        reverse(depth);
        return false;
    }
    public static void reverse(int depth){
        String tmp = "";
        for(int i = arr[depth].length() - 1; i > 0; i--){
            tmp += arr[depth].charAt(i);
        }
        reversed[depth] = reversed[depth] == 0? 1 : 0;
        arr[depth] = tmp;
    }
}