[백준/JAVA] 16943번: 숫자 재배치

📖 문제

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

 

 

 

💡  풀이 방식

• 백트래킹

 

백트래킹으로 정수 A에 포함된 숫자들의 순서를 섞어 숫자 C를 만든다.

이렇게 만든 숫자가 0으로 시작하지 않고, B보다 작은 경우, 정답과 비교해 더 큰 값으로 정답을 갱신한다.

 

 

💥 유의사항

새롭게 만든 C를 문자열로 봤을 때 0으로 시작하는지 확인해야 한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static String[] str;
    static int A,B, N;
    
    static boolean[] chk;
    static List<Integer> list = new ArrayList<>();  // 뽑은 숫자 저장 리스트
    
    static int answer = -1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        str = br.readLine().split(" ");
        A = Integer.parseInt(str[0]);
        B = Integer.parseInt(str[1]);
        
        N = str[0].length();    // 최대 자릿수
        chk = new boolean[N];
        
        dfs(0,0);
        System.out.println(answer);
    }
    
    private static void dfs(int idx, int depth) {
        if(depth == N) {    // 최대 자릿수 N개만큼 뽑았을 때 결과값 비교
            StringBuilder tmp = new StringBuilder();
            for(int i : list) {
                tmp.append(i);
            }
            
            // 0으로 시작하면 패스
            if(tmp.charAt(0) == '0')    return;
            
            int num = Integer.parseInt(tmp.toString());
            if(num < B) {   // 0으로 시작하지 않고, B보다 작으면 정답을 더 큰 값으로 갱신
                answer = Math.max(answer, num);
            }
            
            return;
        }
        
        // 반복문으로 각 자리의 숫자 뽑기
        for(int i = 0 ; i < N ; i++) {
            if(!chk[i]) {
                chk[i] = true;
                list.add(str[0].charAt(i) - '0');
                dfs(i+1, depth+1);
                chk[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

- 사용할 숫자를 리스트에 추가하면서 구하지 않고, 아예 C라는 문자열 변수에 추가했다가 뺐다가 하면서 새로운 숫자 C를 만드셨다.

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

 

 

- 자릿수가 증가할 때 value*10 이렇게 값을 갱신하면서 진행하셨다.

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

 

---

 

 

1회독	2회독	3회독	4회독	5회독
V