백준 10597 순열장난

kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다.

그런데 sujin이 그 파일의 모든 공백을 지워버렸다!

kriii가 순열을 복구하도록 도와주자.

입력
첫 줄에 공백이 사라진 kriii의 수열이 주어진다.

kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다.

출력
복구된 수열을 출력한다. 공백을 잊으면 안 된다.

복구한 수열의 경우가 여러 가지 일 경우, 그 중 하나를 출력한다.

예제 입력                        예제 출력
4111109876532                  4 1 11 10 9 8 7 6 5 3 2

1. 이 문제의 핵심은 수열이 순서를 가지고 있다는 것이다

2. 어느 지점에서 띄워쓰기를 해야할까?

3. 수는 최대 50개의 수로 이루어져 있기 때문에 1부터 50까지의 수로만 이루어져 있다

4. 결국 한개 혹은 두개로만 띄워쓰기를 한다는 말이다.

5. 순서를 가지고 있기 때문에 한개를 띄웠을 때와 두개를 띄웠을 때만 분기를 나눠서 완전탐색(DFS) 해주었고 가지 개수는 두개로 제한된다. depth가 N개인 Tree가 완성.

6. 수열에 같은 숫자가 들어가는 것은 올바르지 않은 수열을 만들기 때문에 그러한 분기로는 들어가지 않게 Visited 배열로 Check해준다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static String s;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = br.readLine();
        int len = s.length();
        // 중복 제거를 위한 마킹
        visited = new boolean[51];
        DFS(0, len, new StringBuilder());
    }
    static void DFS(int depth, int limit, StringBuilder sb) {

        if (depth == limit) {
            if(check(sb.toString())) {
                System.out.println(sb);
                System.exit(0);
            }
            return;
        }
        String st1 = s.substring(depth, depth + 1);

        if(!st1.equals("0")) {
            // 처음거와 두번째거를 넣는다
            String s1 = sb.toString().concat(st1).concat(" ");
            if(depth + 1 <= limit && !visited[Integer.parseInt(st1)]) {
                visited[Integer.parseInt(st1)] = true;
                DFS(depth + 1, limit, new StringBuilder(s1));
                visited[Integer.parseInt(st1)] = false;
            }

            if(depth + 2 <= limit) {
                String st2 = s.substring(depth, depth + 2);

                String s2 = sb.toString().concat(st2).concat(" ");
                if(Integer.parseInt(st2) <= 50 && !visited[Integer.parseInt(st2)]) {
                    visited[Integer.parseInt(st2)] = true;
                    DFS(depth + 2, limit, new StringBuilder(s2));
                    visited[Integer.parseInt(st2)] = false;
                }


            }

        }

    }

    static boolean check(String st) {
        int arr[] = Arrays.stream(st.split(" ")).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(arr);
        int len = arr.length;
        int max = arr[len - 1];
        for(int i = 1; i <= max; i++) {
            if(arr[i - 1] != i) {
                return false;
            }
        }
        return true;
    }
}