[백준OJ] 16943번 숫자 재배치

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

16943번: 숫자 재배치

---

 

풀이

숫자를 입력받은 뒤, Character형으로 모두 쪼개어 저장을 하고 DFS를 이용해서 나올 수 있는 모든 수를 구해준 뒤, B보다 작으면서 가장 큰 숫자를 구해주면 된다.

Character형으로 쪼개준 이유는, 맨 앞에 0이 올 수 없기때문에, 이를 체크해주기 위해서이다.

 

코드

import java.util.Scanner;
import java.util.Vector;

public class Main {
    static int A,B,ret=-1;
    static Vector<Character> v=new Vector<>();
    static boolean[] visited;

    public static void dfs(int cnt,String c){
        if(cnt!=0&&c.charAt(0)=='0') return;

        if(v.size()==cnt){
            int num=Integer.parseInt(c);
            if(num<B) {
                ret=Math.max(ret,num);
            }
            return;
        }
        for(int i=0;i<v.size();i++){
            if(!visited[i]){
                visited[i]=true;
                dfs(cnt+1,c+v.elementAt(i));
                visited[i]=false;
            }
        }
    }

    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        A=scanner.nextInt();
        B=scanner.nextInt();
        while(A>0){
            char c=(char)((A%10)+'0');
            v.add(c);
            A/=10;
        }
        visited=new boolean[v.size()];
        dfs(0,"");
        System.out.println(ret);
    }
}