BOJ 16943

2020-10-08

위 문제는 백준 사이트의 알고리즘 16943 문제에 관한 설명입니다.

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다.

가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작거나 같은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

소스코드


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

public class Main {
	static int[] A;
	static boolean[] select;
	static int B;
	static int answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		answer = -1;
		String str = st.nextToken();
		select = new boolean[str.length()];
		A = new int[str.length()];
		for(int i = 0 ; i < str.length() ; ++i) {
			A[i] = str.charAt(i) - '0';
		}
		B = Integer.parseInt(st.nextToken());
		permutation(0, 0, str.length());
		System.out.println(answer);
	}

	private static void permutation(int number, int cnt, int max) {
		if(cnt == max) {
			if(number > answer) answer= number;
			return;
		}
		for(int i = 0 ; i < max ; ++i) {
			if(select[i] || (cnt == 0 && A[i] == 0)) continue;
			if(number * 10 + A[i] > B) continue;
			select[i] = true;
			permutation(number * 10 + A[i], cnt + 1, max);
			select[i] = false;
		}
	}
}

이번 문제는 완전탐색으로 풀었습니다.

재배치할 숫자는 최대 9개이므로 완전 탐색으로 해결할 수 있는 문제입니다.

A로 생성할 수 있는 모든 숫자를 생성한 뒤에 B보다 작은지 확인하면서 최댓값으로 갱신해주면 됩니다.

숫자 재배치