문제

풀이과정

재귀문제.
문자열의 순서 규칙을 찾아야 한다. 하나씩 늘어나는 문자열을 사전순으로 나열해야한다.
규칙은 다음과 같다.

1. 시작할 문자, 즉 문자열 가운데 가장 빠른 문자 하나를 찾는다.
2. 해당 문자를 기준으로, 앞과 뒤를 보는 이분탐색을 실행한다.
3. 기존 문자 뒤에 올 수 있는 문자 부터 탐색한다. 기존 문자 뒤에 붙는 문자열이, 기존 문자 앞에 있는 문자열보다 사전순으로 앞이기 때문이다.
4. 따라서 문자열은 앞에 생길 수도, 뒤에 생길 수도 있다. 그러므로, 방문체크를 통해 계속 문자열을 반환해주자 (한번 사용한 문자는 또 쓰지 않으며, 동일한 문자가 2개,3개 나올 수도 있기 때문이다.)

정답

public class Main {
    static char[] text;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        text = br.readLine().toCharArray();
        visited = new boolean[text.length];
        DFS(0, text.length);
    }

    private static void DFS(int st, int ed) {
        if(st >= ed) return;

        char[] copyArr = Arrays.copyOfRange(text, st,ed);
        Arrays.sort(copyArr);
        int idx = -1;
        for(int i=st; i<ed; i++) {
            if(text[i] == copyArr[0] && !visited[i]) {
                idx= i;
                break;
            }
        }
        if(idx == -1) return;

        visited[idx] = true;
        String ans = "";
        for(int i=0; i<text.length; i++) {
            if(visited[i]) ans += text[i];
        }
        System.out.println(ans);
        DFS(idx+1, ed);
        DFS(st,idx);
    }
}