[ 백준 / BOJ 16943 ] 숫자 재배치 ( 자바 / JAVA )

https://www.acmicpc.net/problem/16943

16943번: 숫자 재배치

 

문제

---

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

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

 

입력

---

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

 

출력

---

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

 

풀이

---

DFS를 이용

DFS 로 A를 다양한 수로 조합하고 모두 사용했다면 B와 비교 후, 작은 값이면 기존의 값과 더 큰 값을 선택 ‼️

코드

---

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

public class Main_BOJ_16943_숫자재배치 {
    static String A, B, C;
    static int a,b,c;
    static boolean[] isVisited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());

        A = stringTokenizer.nextToken();
        B = stringTokenizer.nextToken();
        C = "";

        a = Integer.parseInt(A);
        b = Integer.parseInt(B);
        c = -1;

        isVisited = new boolean[A.length()];

        DFS();

        System.out.println(c);
    }
    private static void DFS() {

        if(C.length() == A.length()){
            if(Integer.parseInt(C) < b)
                c = Math.max(c, Integer.parseInt(C));
            return;
        }

        for(int i = 0 ; i < A.length(); i++){
            if((C.length() == 0 && A.charAt(i) == '0') || isVisited[i])   continue;

            isVisited[i] = true;
            C += A.charAt(i);
            DFS();
            isVisited[i] = false;
            C = C.substring(0, C.length()-1);
        }
    }
}