백준 2922번 크면서 작은 수 (JAVA)

문제

난이도

실버 3

알고리즘 분류

문자열
브루트포스 알고리즘
백트래킹

풀이

주어진 수를 모두 이용하여 새로운 수를 만들기(자리 수를 유지해야한다.)

주어진 수를 모두 이용하기 때문에 순열을 생성한다.

주어진 수보다 크지만 그 중 가장 작은 수를 탐색해야하기 때문에 정렬 후 순열을 생성하여 작은 값부터 탐색한다.

코드

public class Main {

    private static char[] split;
    private static int value;

    private static int N;
    private static int[] numbers;
    private static boolean[] visited;
    private static int answer;

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        String input = in.readLine();

        value = Integer.valueOf(input);             // 주어진 수
        split = input.toCharArray();
        Arrays.sort(split);                         // 순서대로 순열을 생성하기 위해 정렬 후 순열 생성

        N = split.length;

        numbers = new int[N];
        visited = new boolean[N];

        answer = 0;

        perm(0);

        sb.append(answer);
        out.write(sb.toString());
        out.close();
    }

    private static void perm(int cnt) {
        if (answer != 0) {                          // 정답을 이미 구했다면
            return;                                 // 탐색할 필요 없다.
        }

        if (cnt == N) {                             // 순열 생성시
            if (split[0] > split[numbers[0]]) {     // 새롭게 구성하는 수의 맨 앞자리가 주어진 수보다 작다면 어떠한 경우에도 주어진 수보다 작다.
                return;                             // 검사할 필요가 없다. 가지치기
            }

            String strTemp = "";
            for (int i = 0; i < N; i++) {
                strTemp += split[numbers[i]];       // 생성한 순열로 새로운 문자열 생성
            }

            int temp = Integer.valueOf(strTemp);    // 숫자 비교를 위해 문자열을 int로 변환

            if(value < temp) {
                answer = temp;                      // 최조 주어진 수 보다 큰 값이 나오는 경우에 해당
            }

            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                numbers[cnt] = i;
                visited[i] = true;
                perm(cnt + 1);
                visited[i] = false;
            }
        }
    }
}