백준 14629번
https://www.acmicpc.net/problem/14629
문제
생각하기
- 백트래킹 문제이다.
- 숫자의 범위가 int형을 넘어서므로 Long을 써야한다.
- 몇가지의 경우를 따져봐야한다.
- 가령, 9999의 숫자와 가장 차이가 적은 숫자를 찾는다고 했을 때, 9999는 4자리의 숫자이지만, 5자리의 숫자와 가장 적은 차이를 가질 수도 있기 때문에 자리수를 바꿔가면서도 탐색을 해야 한다.
동작
if (N >= MAXLIMIT) { // 숫자의 길이가 10이상일 경우, 숫자로 만들 수 있는 최대값이 됨
System.out.println("9876543210");
return;
}
9876543210을 넘는 숫자일 경우, 어차피 최소의 차이를 가지는 숫자는 9876543210이기 때문에 바로 출력하고 return 하도록 했다
visit = new boolean[10];
if (len != 2) {
visit[9] = true;
DFS("9", 0, len - 2);
visit[9] = false;
}
visit[Character.getNumericValue(strN.charAt(0))] = true;
DFS( Character.toString(strN.charAt(0)) , 0, len - 1);
visit[Character.getNumericValue(strN.charAt(0))] = false;
if(len != 10) {
visit[1] = true;
DFS("1", 0, len);
visit[1] = false;
}
여기가 중요하다
만약 숫자의 길이가 2이상이면서 10이하의 경우,
예시로 들자면 3자리수 333의 경우, 2자리의 숫자와 4자리 숫자까지 포함하여 최솟값을 탐색하여야된다.
자릿수를 한자리 줄이는 경우에서는 9를 기준으로만 탐색하면 된다.
333의 경우, 최솟값을 만들 수 있는 값은 당연히 아래 자릿수에서는 9로 시작하는 98이 될 것 이기 때문이다.
하나의 자리수를 변경하면서 사용된 수는 다시 사용해야 하기 때문에 visit을 false처리 해줘야한다.
중간에 있는 DFS는 찾는 자릿수와 같은 자릿수의 최솟값을 찾는다.
3번째에 있는 DFS는 한자리 위의 자릿수 최솟값을 찾는다. 333의 경우, 우리는 1로 시작하는 수 즉, 1023가 최솟값이 될 것이기 때문에 1의 자리로 시작하는 경우만 찾으면 된다.
그리고 문제에서 예외로 최솟값이 같은 값이 여러개일 경우, 가장 작은 값을 출력하라고 되어있기 때문에 DFS에서 같은 값의 경우도 if문으로 따로 만들어줘야 하지만,
자리수 별로 DFS탐색하는 순서만 다시 맞춰주면, 굳이 비교하는 if문이 필요하지 않게된다.
여기서는 3자리 수 기준이라면, 2자릿수 DFS -> 3자릿수 DFS -> 4자릿수 DFS 순으로 탐색한다.
이 순서로 진행하면 굳이 같은 값의 경우 최솟값 비교가 필요하지 않게 된다.
그 이유는, 9로 시작해서 간격을 줄이는 아래자릿수 보다 1로 시작하는 윗자릿수가 더 최솟값을 가깝게 갈 수 있다.
333의 경우 1023 - 333 = 690, 333 - 98 = 235, 333 - 321 = 12가 된다.
어차피 아래에서 최솟값을 갱신할 수 없는 경우면 중간에서 해결이 가능하다.
(메소드를 실행하는 순서도 중요하다는 것을 새삼느끼고 간다.)
코드
Java
import java.io.*;
public class Main {
private static final long MAXLIMIT = 9876543210L;
static boolean visit[];
static String strN;
static long min = Long.MAX_VALUE;
static String result;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
strN = br.readLine();
long N = Long.parseLong(strN);
int len = strN.length();
if (N >= MAXLIMIT) { // 숫자의 길이가 10이상일 경우, 숫자로 만들 수 있는 최대값이 됨
System.out.println("9876543210");
return;
} else if (N <= 10) {
System.out.println(N);
return;
}
visit = new boolean[10];
if (len != 2) {
visit[9] = true;
DFS("9", 0, len - 2);
visit[9] = false;
}
visit[Character.getNumericValue(strN.charAt(0))] = true;
DFS( Character.toString(strN.charAt(0)) , 0, len - 1);
visit[Character.getNumericValue(strN.charAt(0))] = false;
if(len != 10) {
visit[1] = true;
DFS("1", 0, len);
visit[1] = false;
}
System.out.println(Long.parseLong(result));
} // End of main
private static void DFS(String num, int depth, int depthLimit) { // 백트래킹
if (depth == depthLimit) {
long temp = Long.parseLong(num);
long diff = Math.abs(Long.parseLong(strN) - temp);
if (min > diff) {
min = diff;
result = num;
}
return;
}
for (int i = 0; i < 10; i++) {
if (visit[i])
continue;
visit[i] = true;
DFS( num + Integer.toString(i), depth + 1, depthLimit);
visit[i] = false;
}
} // End of DFS
} // End of Main classKotlin
