[Baekjoon] 백준 2992번: 크면서 작은 수 (JAVA)

문제 2992

2992번: 크면서 작은 수

[ 문제 풀이 ]

순열 문제로, DFS를 활용하면 됩니다. depth 매개변수를 통해서 숫자가 모두 조합되었을 때 즉, depth가 X의 길이와 같아졌을 때, 정수 X보다 크고 현재 min 값보다 작으면 min을 현재 조합된 숫자로 업데이트해줍니다.

X보다 큰 수 중 작은 값을 min이라고 하고, 초기값은 Integer.MAX_VALUE로 초기화해줍니다.

[ 코드 ]

import java.io.*;

public class Main {
    private static String x;
    private static char[] arr, input;
    private static boolean[] visit;
    private static int size;
    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        x = br.readLine();
        size = x.length();
        arr = new char[size];
        input = new char[size];
        visit = new boolean[size];

        for (int i = 0; i < size; i++) {
            arr[i] = x.charAt(i);
        }

        permutation(0);
        if (min == Integer.MAX_VALUE) bw.write("0");
        else bw.write(String.valueOf(min));

        bw.flush();
    }

    private static void permutation(int depth) {
        if (depth == size) {
            int res = Integer.parseInt(new String(input));
            if (res > Integer.parseInt(x)) {
                if (min > res) min = res;
            }
            return;
        }

        for (int i = 0; i < size; i++) {
            if (!visit[i]) {
                input[depth] = arr[i];
                visit[i] = true;
                permutation(depth+1);
                visit[i] = false;
            }
        }
    }
}