[백준 10597] 순열장난

 

문제의 해석이 좀 난해했다.

지문에서 알 수 있는 것은

1. 수는 1부터 N까지로 구성되어 있으며 연속된 수열이 아니면 제대로 복구된 수열이 아니다.

2. 수는 50을 넘지 않는다.

 

위 힌트를 바탕으로 풀이해보자.

1. DFS + 백트래킹으로 접근한다.

2. 수의 사용여부를 기록하는 배열을 만들어서 한번만 사용할 수 있게 한다.

3. 2의 조건을 만족할때 한글자씩 탐색한다.

4. 2의 조건을 만족하고 두글자가 50이하일 경우 탐색한다.

5. 입력받은 수열의 끝까지 탐색을 마칠 경우 수열을 검사하고 만족시 종료한다.

 

public class Main {
    
    static String s;
    static boolean used[] = new boolean[51];
    static int a[] = new int[50];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        s = br.readLine();
        dfs(0, 0);
    }
    
    public static void dfs(int idx, int fill) {
        if(idx >= s.length()) {
            int e = 50;
            for(int i=1; i<=50; i++) {
                if(!used[i]) {
                    e = i-1;
                    break;
                }
            }
            int cnt = 0;
            for(int i=0; i<50; i++)
                if(a[i] != 0)
                    cnt++;
            
            if(e != cnt) return;
            print();
            System.exit(0);
        }
        
        int n = Integer.parseInt(s.substring(idx, idx+1));
        
        if(!used[n]) {
            used[n] = true;
            a[fill] = n;
            dfs(idx + 1, fill + 1);
            used[n] = false;
            a[fill] = 0;
        }
        
        if(idx + 1 < s.length()) {
        	int k = Integer.parseInt(s.substring(idx, idx+2));
        
        	if(k <= 50 && !used[k]) {
            	used[k] = true;
            	a[fill] = k;
            	dfs(idx + 2, fill + 1);
            	used[k] = false;
           		a[fill] = 0;
        	}
        }
    }
    
    public static void print() {
        for(int i=0; i<50; i++)
            if(a[i] != 0)
                System.out.print(a[i] + " ");
    }
}