Problem Solving/Baekjoon
[백준] 2992 크면서 작은 수 - Backtracking / Java
graycode
2023. 2. 22. 20:49
• 문제 링크
2992번: 크면서 작은 수
정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이
www.acmicpc.net
• 풀이 과정
• 풀이 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static char[] arr;
static boolean[] visit;
static int num, len, min = Integer.MAX_VALUE;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String x = br.readLine();
arr = x.toCharArray();
num = Integer.parseInt(x);
len = x.length();
visit = new boolean[len];
recur(0);
bw.write(String.valueOf(min == Integer.MAX_VALUE ? "0" : min));
bw.flush();
}
private static void recur(int depth) {
if (depth == len) {
int tmp = Integer.parseInt(sb.toString());
if (tmp > num && tmp < min)
min = tmp;
return;
}
for (int i = 0; i < len; i++) {
if (visit[i])
continue;
visit[i] = true;
sb.append(arr[i]);
recur(depth + 1);
visit[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
}
}