"숫자 재배치" - 16943번 S1

🎃문제설명

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

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

입력

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

출력

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

🔒제한사항

• $1 ≤ A, B < 10^9$

💾입출력 예

입력	출력
1234 3456	3421
1000 5	-1
789 123	-1

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론

🌟문제 이해 및 풀이계획

✏️정수 A를 조합할 때 순서에 영향이 있으므로 순열을 이용한다.

✏️가능한 C를 모두 구하고 B와 비교하면서 가장 큰 C의 값을 구한다.

✏️C의 맨 첫자리가 0이 되면 안되므로 arr[0]이 0이면 return해준다.

✍🏻내 코드1 - 정답코드

package BOJ;

import java.util.Scanner;

/*
 * 2021.12.11 daily algo/commit
 * 
 * Brute Force, Permutation
 */

public class boj_16943 {
	
	static int max = -1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String A = sc.next();
		int B = sc.nextInt();
		
		int[] nums = new int[A.length()];
		int[] arr = new int[A.length()];
		boolean[] visited = new boolean[A.length()];
		for(int i=0; i<A.length(); i++) {
			nums[i] = A.charAt(i) - '0';
		}
		
		permutation(nums, arr, visited, A.length(), 0, B);
		System.out.println(max);
		
		sc.close();
	}
	
	public static void permutation(int[] nums, int[] arr, boolean[] visited, int n, int depth, int B) {
		if(depth == n) {
			int num = 0;
			if(arr[0] == 0) return;
			for(int i=0; i<n; i++) {
				num += arr[i] * Math.pow(10, n-i-1);
			}
			if(num > B) return;
			if(max < num) max = num;
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(!visited[i]) {
				visited[i] = true;
				arr[depth] = nums[i];
				permutation(nums, arr, visited, n, depth+1, B);
				visited[i] = false;
			}
		}
	}

}

강의내용

✔️시간 복잡도 : $2^{10} (A<=1,000,000,000)$ => 10자리여도 순서를 바꾸면 0이 무조건 맨 처음 가게되므로 9자리가 가장 큰 값이 된다.
=> 9! = 3628800(약 30만개)

✔️순열 or 재귀를 이용해서 풀 수 있다.