[BOJ 16943] 숫자 재배치 (Java)

BOJ 16943 숫자 재배치

문제풀이

보자마자 순열이니까! 그리고 특정 수 보다 작은 가장 큰 수니까! 수를 정렬해서 가장 작은 순열부터 nextPermutation으로 특정 수 보다 커지는 시점에 그만두면 되겠다고 생각했다. 막상 구현을 해보니 -1이 나와야하는 경우 즉, 제일 앞 자리에 0이 나오면 안된다는 조건이 보였고 그에 따라 추가적인 구현을 해야했다. 추가 구현을 완료한 후에도 런타임 에러를 뿜어냈고 코드는 복잡했다. 그래서 다시 처음부터 문제를 보기 시작했다.

다시 본 문제는 아주 간단했다. 완전탐색으로 순열을 만들면서 조건을 만족하는 경우에만 ans를 갱신해나가면 되는 것이였다. 코드도 깔끔하면서 짧아졌다.

시간제한이 문제되지 않는 선에서 알고리즘 풀이는 완전탐색이 항상 옳다. 아이디어가 떠올랐다고 해서 바로 시도하는 것이 아니라 검증의 과정을 거치도록하자.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[] a;
	static boolean[] selected;
	static int b;
	static int ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		ans = -1;
		
		char[] temp = st.nextToken().toCharArray();
		selected = new boolean[temp.length];
		a = new int[temp.length];
		b = Integer.parseInt(st.nextToken());
		
		for(int i = 0 ; i < temp.length ; ++i) {
			a[i] = temp[i] - '0';
		}
		
		permutation(0, 0, temp.length);
		
		System.out.println(ans);
	}

	private static void permutation(int number, int cnt, int max) {
		if(cnt == max) {
			ans = number > ans ? number : ans;
			return;
		}
		
		for(int i = 0 ; i < max ; ++i) {
			if(selected[i] || (cnt == 0 && a[i] == 0)) continue;
			if(number * 10 + a[i] > b) continue;
				
			selected[i] = true;
			permutation(number * 10 + a[i], cnt + 1, max);
			selected[i] = false;
		}
	}
}