[JAVA]백준 1039번: 교환

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

1039번: 교환

1. 문제 설명

 

0으로 시작하지 않는 정수 N(1,000,000보다 작거나 같은 자연수) 이 주어진다. 이때 M을 정수 N의 자릿수라고 할 때 다음과 같은 연산을 K (10보다 작거나 같은 자연수 ) 번 수행한다.

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

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 문제.

 

만약 K번 수행할 수 없으면 -1을 출력한다.

 

2. 풀이

 

bfs로 풀 수 있는 문제이다.

 

문제 그대로, i번 위치의 숫자와 j번 위치의 숫자를 바꾸는 것을 K번 수행한 후 그중 최댓값을 구하는 것을 구현하면 된다.

 

visited 배열을 사용하지 않고 최대 7자리의 숫자를 최대 10번 i번째 위치와 j번째 위치를 바꾼다고 생각하면 시간 초과가 발생할 것이다.

 

7*6/2 ^ 10 =  16,679,880,978,201

 

하지만 중요한 점은 문제에서 N이 1,000,000보다 작거나 같은 자연수라고 언급한 것이다.

 

이 뜻은 N을 K번 연산을 수행하더라도 바뀐 수가 1,000,000보다 작거나 같은 수라는 점이고, 최대 가능한 경우의 수는 1,000,000 * 10이다.

 

이를 이용하여 1,000,000 크기의 visited 배열을 사용, 현재 depth에서 이미 만들어진 수는 또다시 연산을 수행하지 않도록 한다.

 

따라서 시간 복잡도는 O(NK)이고, 충분히 2초 안에 계산이 가능하다.

 

코드에서는 boolean [1,000,000][K] 대신 int [K] 배열을 사용했는데, 메모리와 시간을 줄이기 위해서 int [] 배열을 사용했다.

 

boolean [][] 배열 사용 시 A번째 연산을 수행 한 수가 B라고 할 때 boolean [A][B]가 false라면 다음 연산에 사용한다.

 

int [] 배열 사용 시 A번째 연산을 수행한 수가 B라고 할 때  int [B]의 값이 A보다 작으면 다음 연산에 사용한다.

 

무엇을 사용하든 로직에 큰 차이는 없다.

 

두 번째로 신경 써야 하는 점은 주어진 연산을 K번 수행할 수 없는 경우이다.

 

연산을 수행할 수 없는 경우는 바꾼 수가 0으로 시작할 때 밖에 없다.

 

따라서 바꾼 수가 0으로 시작하는 경우 queue에 추가하지 않으며, 아직 K번 연산을 수행하지 않았음에도 queue에 원소가 없는 경우 -1을 출력한다.

 

 

 

 

 

 

 

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    public static int[] visited = new int[1000001];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N, K;

        Queue<Integer> list = new LinkedList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int length = 0;

        while (N / (int) Math.pow(10, length) != 0) {
            length++;
        }

        // queue에 처음 N 추가
        list.add(N);

        while (!list.isEmpty() && K > 0) {
            int size = list.size();

            for (int x = 0; x < size; x++) {
                int now = list.poll();

                // change
                for (int i = 0; i < length - 1; i++) {
                    for (int j = i + 1; j < length; j++) {
                        int next = swap(now, i, j);

                        // 앞자리가 0이거나 현재 depth에서 방문한 적이 있는 경우 queue에 add하지 않음.
                        if (next != 0 && visited[next]!=K) {
                            list.add(next);
                            visited[next] = K;
                        }
                    }
                }
            }

            K--;
        }

        if (list.isEmpty()) {
            System.out.println("-1");
        } else {

            int ans = 0;

            for (int x : list) {
                ans = Math.max(x, ans);
            }

            System.out.println(ans);
        }


    }

    // 교환
    public static int swap(int now, int i, int j) {


        char[] list = String.valueOf(now).toCharArray();

        char temp = list[i];
        list[i] = list[j];
        list[j] = temp;


        // 앞자리가 0이면 error

        if(list[0]=='0')
            return 0;


        return Integer.parseInt(new String(list));
    }


}

첫번째 : int[]배열로 방문 체크, 두 번째 boolean[][] 배열로 방문 체크