문제

이해

정수 N이 있고 M은 N의 자릿수입니다.

N은 최대 1,000,000이기 때문에 M은 최대 7이 됩니다.

K를 입력받고 다음의 연산을 K번 수행합니다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

연산의 의미는 단순히 자릿수의 숫자끼리 위치를 바꾸되, 최종적으로 바뀐 수가 0으로 시작하면 안되는 것입니다.

K번 연산을 수행한 뒤 만들 수 있는 가장 큰 수를 출력하면 됩니다.

접근

문제의 중요한 조건은 K번의 연산을 무조건 수행해야 한다는 것입니다. (132, 3)의 입력의 경우에는 132로 만들 수 있는 최대값은 321이지만 연산을 무조건 3번 수행해야 하기 때문에 이 때의 정답은 312가 되는 것입니다.

문제를 보았을 때 우선적으로는 최댓값을 만드는 것이기 때문에 그리디로 생각할수도 있지만 M이 최대 7 그리고 K가 최대 10이라는 것을 보면 완탐의 가능성을 확인할 수 있습니다.

완전탐색의 경우 시간복잡도를 분석해봅시다. 최대 7 자릿수에서 2개를 뽑고 그 과정을 K번 수행하면 됩니다.

7C2 ^ 10 = 1.6679881e+13

위와 같은 방법으로는 불가능해보입니다. 그렇다면 탐색의 과정에서 중복을 제거할 수 있는 방법을 찾아봅시다. 우선, 중복이 생기는 경우를 생각해보면, 탐색의 중복은 특정 횟수의 연산을 수행했을 때 과정이 어떻든 결과가 같은 경우에 해당합니다. 예를들어, a번 수행하면 132가 나왔다면 우리는 a번 이전에 어떻게 숫자를 교환했는지는 궁금하지 않습니다. 단지, a번 수행했을 때의 결과만이 중요합니다.

따라서, 완전탐색을 수행할 때 숫자와 연산횟수를 기준으로 방문처리를 하고 중복탐색을 제거하면 시간복잡도를 획기적으로 줄일 수 있을 것 같습니다.
(대충 계산해보면 N이 가능한 수의 갯수 * 연산 횟수로 1,000,000 x 10 즉, 1000만의 시간복잡도가 계산됩니다.)
(하지만, 실제로는 바꾼 수가 0이 될 수 없다는 조건 등으로 시간복잡도는 더 작습니다.)

풀이

private static int bfs() {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(A);
        visited[A][0] = true;
        int depth = 0;

        while (++depth <= B) {
            int qsize = q.size();
            while (qsize-- > 0) {
                int cur = q.poll();

                for (int i = 0; i < size; i++) {
                    for (int j = i + 1; j < size; j++) {
                        int result = Swap(cur, i, j);

                        if (String.valueOf(result).length() != size || visited[result][depth]) {
                            continue;
                        }

                        visited[result][depth] = true;
                        q.add(result);
                    }
                }
            }
        }

        if(q.size() == 0){
            return -1;
        }

        int max = 0;
        for (int n : q) {
            max = Math.max(max, n);
        }

        return max;
    }

BFS를 수행하는 코드입니다. visited[1000001][B+1]만큼 생성하였고 방문처리를 수와 연산 수를 기준으로 수행합니다.

전체 코드

package baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class prob1039 {
   static class Node {
       int a;
       int b;
       int result;

       public Node(int a, int b, int result) {
           this.a = a;
           this.b = b;
           this.result = result;
       }
   }

   static boolean[][] visited;
   static int A, B;
   static int size;

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

       Scanner sc = new Scanner(System.in);
       A = sc.nextInt();
       B = sc.nextInt();
       size = String.valueOf(A).length();
       visited = new boolean[1_000_001][B + 1];

       if (String.valueOf(A).length() == 1) {
           System.out.println(-1);
           return;
       }

       System.out.println(bfs());
   }

   private static int bfs() {
       Queue<Integer> q = new ArrayDeque<>();
       q.add(A);
       visited[A][0] = true;
       int depth = 0;

       while (++depth <= B) {
           int qsize = q.size();
           while (qsize-- > 0) {
               int cur = q.poll();

               for (int i = 0; i < size; i++) {
                   for (int j = i + 1; j < size; j++) {
                       int result = Swap(cur, i, j);

                       if (String.valueOf(result).length() != size || visited[result][depth]) {
                           continue;
                       }

                       visited[result][depth] = true;
                       q.add(result);
                   }
               }
           }
       }

       if(q.size() == 0){
           return -1;
       }

       int max = 0;
       for (int n : q) {
           max = Math.max(max, n);
       }

       return max;
   }

   private static int Swap(int n, int a, int b) {
       String N = String.valueOf(n);

       char[] cArr = N.toCharArray();
       char tmp = cArr[a];
       cArr[a] = cArr[b];
       cArr[b] = tmp;

       return Integer.parseInt(String.valueOf(cArr));
   }
}

결과

리뷰

아이디어는 빠르게 떠올렸으나 문자열 처리를 어떻게할지 고민하다가 오래 걸린 문제였습니다.