[BOJ/Java] 1039. 교환

📌 [BOJ/Java] 1039. 교환

• 문제 링크

---

💡 문제 해석

자연수 N(최대 1,000,000)과 교환 횟수 K(최대 10)가 주어진다.
숫자 N의 각 자릿수를 정확히 K번 교환하여 만들 수 있는 가장 큰 수를 구해야 한다.
단, 0으로 시작하는 숫자는 불가능하므로, 교환 결과가 0으로 시작하면 해당 경우는 제외해야 한다.

예를 들어,
✅ N = 132, K = 1일 때 → (312, 231) 중 312가 최대
✅ N = 100, K = 1일 때 → 가능한 교환이 없으므로 -1

문제의 핵심은 BFS(너비 우선 탐색)를 사용하여 가능한 모든 숫자 조합을 탐색하는 것이다.

---

📝 풀이 과정

1️⃣ BFS를 활용한 완전 탐색

• 현재 숫자 상태를 Queue에 저장하고, Set을 활용해 방문 여부를 체크한다.
• K번 동안 모든 가능한 숫자 조합을 생성하여 탐색한다.
• 매 반복마다 가능한 모든 자리 교환을 수행한다.

2️⃣ 숫자 교환 로직

• 문자열로 변환하여 두 자리 숫자를 교환한다.
• 교환 후 0으로 시작하는 경우 제외한다.

3️⃣ 최대 숫자 찾기

• K번의 교환이 끝난 후, 남아 있는 숫자들 중 가장 큰 값을 출력한다.
• 만약 유효한 숫자가 없다면 -1 출력

---

💻 코드 (Java)

import java.util.*;

public class Main {
    static int N, K;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        
        System.out.println(bfs());
    }
    
    private static int bfs() {
        Queue<String> queue = new LinkedList<>();
        queue.offer(String.valueOf(N));
        
        for (int k = 0; k < K; k++) {
            Set<String> visited = new HashSet<>();
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                
                for (int x = 0; x < cur.length(); x++) {
                    for (int y = x + 1; y < cur.length(); y++) {
                        char[] arr = cur.toCharArray();
                        
                        // 자리 바꾸기
                        char temp = arr[x];
                        arr[x] = arr[y];
                        arr[y] = temp;
                        
                        // 교환 후 숫자가 0으로 시작하면 제외
                        if (arr[0] == '0') continue;
                        
                        String next = new String(arr);
                        
                        // 중복된 경우 방문 X
                        if (!visited.contains(next)) {
                            visited.add(next);
                            queue.offer(next);
                        }
                    }
                }
            }
            
            // 교환을 했음에도 불구하고 더 이상 탐색할 수 없으면 -1 반환
            if (queue.isEmpty()) return -1;
        }
        
        int maxVal = -1;
        while (!queue.isEmpty()) {
            maxVal = Math.max(maxVal, Integer.parseInt(queue.poll()));
        }
        return maxVal;
    }
}

---

⏱ 시간 복잡도 분석

• BFS 탐색을 사용하며, 최대 K=10번 반복
• 숫자 교환 시, 최대 O(L^2) (L은 숫자의 자릿수, 최대 6)
• 최악의 경우 O(K × L^2) ≈ O(10 × 36) = O(360) → 충분히 해결 가능

---

🧐 느낀 점

• 단순한 브루트포스 방식으로는 해결이 어려운 문제였다.
• BFS를 활용하여 교환 과정을 단계별로 진행하는 것이 핵심이었다.
• 숫자를 문자열로 변환하여 다루는 방식이 자주 사용되므로 익숙해져야겠다.
• 0으로 시작하는 숫자를 배제하는 조건을 놓치지 않도록 주의해야겠다.