[백준 10597] 순열장난(Java)

문제 링크 : https://www.acmicpc.net/problem/10597

이 문제는 백트래킹을 이용하여 풀 수 있습니다. 문제에서 주어진 조건이 최대 50개의 수로 이루어진 순열이므로 조건의 제한 범위가 작아 백트래킹으로 충분히 진행 가능하고, 문자열을 각각 한 글자씩과 두 글자씩 나누어 최종적으로 모든 문자열을 나누었을 때 check 배열의 1부터 지금까지 나눈 수 중 가장 큰 수까지 모두 체크가 되어있는지를 확인하여 만약 그렇다면 해당 순열을 출력합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static String str;
    static int N;
    static boolean[] check = new boolean[51];

    static void backtracking(int idx, int max, String ans){
        if(idx==N){
            for(int i=1;i<=max;i++){
                if(!check[i]) return;
            }

            System.out.println(ans);
            System.exit(0);
        }

        String s = str.substring(idx,idx+1);
        int num = Integer.parseInt(s);
        if(!check[num]){
            check[num] = true;
            backtracking(idx+1, (num>max)? num : max, ans+" "+s);
            check[num] = false;
        }

        if(idx < N-1){
            s = str.substring(idx, idx+2);
            num = Integer.parseInt(str.substring(idx, idx+2));
            if(num<51 && !check[num]){
                check[num] = true;
                backtracking(idx+2, (num>max)? num : max, ans+" "+s);
                check[num] = false;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        N = str.length();
        backtracking(0, 0, "");

    }
}