16945 숫자 재배치 Java

16945 숫자 재배치 Java

문제 🌐

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

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

입력

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

출력

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

접근 방법

순열을 구하고 앞자리가 0인 경우에는 제외했어야 하는데 바보처럼 삽질 했다….

그리고 A의 길이가 B의 길이보다 길면 B보다 작은 순열이 나올 수 없으므로 순열 함수에 진입하기 전에 답을 출력했다!

꼼꼼하게 체크하고 풀어야 시험에서도 문제가 없을 텐데... 앞으로는 정신 차리고 풀어야겠다.

Full Solution

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int answer = -1;
	static int B;
	static int N;
	static int A;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		A = sc.nextInt();
		String[] arr = ("" + A).split("");
		N = arr.length;
		B = sc.nextInt();
		boolean[] chk = new boolean[N];
		if (arr.length > ("" + B).length())
			System.out.println(-1);
		else {
			permutation(chk, arr, "", arr.length);
			System.out.println(answer);

		}

	}

	static void permutation(boolean[] chk, String[] arr, String result, int cnt) {
		if (result.length() == cnt) {
			if (result.charAt(0) == '0') return;
			if (Integer.valueOf(result) < B)
				answer = Math.max(answer, Integer.valueOf(result));
			return;
		}

		for (int i = 0; i < N; i++) {
			if (result.length() == 0 && arr[i].equals("0"))
				continue;
			if (!chk[i]) {
				chk[i] = true;
				permutation(chk, arr, result + arr[i], cnt);
				chk[i] = false;
			}
		}
	}

}