[BOJ/Java] 16943. 숫자 재배치

[BOJ/Java] 16943. 숫자 재배치

16943번: 숫자 재배치

---

풀이

package edu.ssafy.im.BOJ.S1.No16943;

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

public class Main {
    static int selected[]; // 순열을 만들기 위한 배열
    static boolean visited[]; // 해당 숫자가 이미 선택되었는지 확인하는 배열
    static List<Integer> arrA; // 정수 A를 숫자로 변환하여 저장할 리스트
    static int B; // 정수 B
    static int ans = -1; // 결과값을 저장할 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        String A = (st.nextToken()); // A 입력
        arrA = new ArrayList<>(); // A의 각 자리 숫자를 저장할 리스트
        B = Integer.parseInt(st.nextToken()); // B 입력
        int B_length = Integer.toString(B).length(); // B의 자리수 계산

        selected = new int[Math.min(B_length, A.length())]; // 선택된 숫자를 저장할 배열 초기화
        visited = new boolean[A.length()]; // 방문 여부를 저장할 배열 초기화

        // A의 각 자리 숫자를 리스트에 저장
        for (char c : A.toCharArray()) {
            arrA.add(Character.getNumericValue(c));
        }
        Collections.sort(arrA); // A를 오름차순으로 정렬

        // B의 자리수가 A보다 크거나 같은 경우에만 순열을 만들어서 확인
        if (B_length >= arrA.size()) {
            recursive(0, 0);
        }

        System.out.println(ans); // 결과 출력
    }

    private static void recursive(int idx, int k) {
        if (idx == selected.length) { // 순열이 완성된 경우
            int cnt = 1;
            int num = 0;
            for (int i = selected.length - 1; i >= 0; i--) {
                num += selected[i] * cnt; // 숫자 만들기
                cnt *= 10;
            }
            // 만들어진 숫자가 B보다 작고, 자리수가 맞는 경우
            if (num < B && Integer.toString(num).length() == selected.length) {
                ans = num; // 결과값 갱신
            }
            return;
        }
        for (int i = 0; i < arrA.size(); i++) {
            if (!visited[i]) { // 해당 숫자가 아직 선택되지 않은 경우
                // 숫자 선택 후 재귀 호출
                visited[i] = true;
                selected[idx] = arrA.get(i);
                recursive(idx + 1, k + 1);
                visited[i] = false;
            }
        }
    }
}