[백준] 교환(1039) Java

문제 링크

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

1039번: 교환

 

문제 요약

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

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

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

 

접근법

BFS를 활용하여 완전탐색을 하되, 이미 탐색한 숫자는 다시 탐색하지 않게끔 조건을 줘서 시간 내에 문제를 풀 수 있게 하였다.

 

만약 BFS로 조건 없이 완전 탐색을 하면 시간 복잡도는 다음과 같다.

swap 연산을 하기 위해 숫자를 두개 선택하는 경우의 수는 M개의 숫자 중 중복 없이 2개를 선택하는 경우의 수이므로 MC2.

N의 최댓값이 1,000,000이므로 M의 최댓값은 7. 따라서 MC2의 최댓값은 7C2 = 21.

즉 7자리 숫자 1개에서 swap을 통해 만들어낼 수 있는 숫자는 21개.

 

swap을 최대 K번 해야 하므로, K번 swap을 통해 만들어지는 최종 숫자들의 개수는 중복을 고려하지 않으면 21^K개 이다.

K의 최댓값이 10이므로, 21^10 = 16,679,880,978,201.

이렇게 많은 수의 숫자들을 만들고, 그 중 최댓값을 찾는 것은 제한 시간인 2초 안에는 불가능하다.

 

하지만 각 swap stage (swap stage는 예를 들어 숫자 123에서 swap을 통해 [213, 321, 132]을 만드는 것을 한 stage라고 한다. 그 다음 stage는 1번의 swap을 거친 [213, 321, 132] 세 숫자에 각각 swap을 해서 총 9개의 숫자를 만드는 stage이다. 마찬가지로 다음 stage는 9개의 숫자에 swap을...(후략)) 에서 swap을 해서 나온 x개의 숫자 중 겹치는 숫자들을 제외하는 조건을 걸어준다면, 21^10보다 적은 횟수로 모든 경우의 숫자에 대한 탐색이 가능해진다. 

 

예를 들어 첫 번째 stage에서 123에서 swap을 통해 [213, 312, 132]을 만들었을 때,

두 번째 stage에서는 [213, 312, 132]로 swap을 해서 9개의 숫자 [123, 312, 231, 132, 213, 321, 312, 231, 123]을 만든다.

이 때 123, 312, 231 이렇게 3개의 숫자가 중복되어서 나오므로, 중복을 제거해주면 [123, 312, 231, 132, 213, 321] 이렇게 6개의 숫자만 남는다. 그러면 다음 stage에서는 이 6개의 숫자만 가지고 swap을 하는 것이다.

 

이 중복 제거는 HashSet을 이용하여 구현하였다.

중복을 제거한 숫자들을 queue에 넣고, 이전 stage에서 enequeue한 모든 숫자를 dequeue하면 하나의 stage가 끝나는 식이다.

그리고 stage의 구분은, 이전 stage에서 swap을 통해 만들어 낸, 중복을 제거한 새로운 숫자의 개수를 통해서 구분해줬다.

 

예를들어 123의 경우는 123을 queue에 넣고 시작하므로 첫 번째 stage에서는 1개의 dequeue만 하면 되고,

두 번째 stage에서는 이전 stage에서 3개의 숫자를 넣었으므로 dequeue 3번, 다음 stage에서는 중복을 제거한 6개의 숫자만 넣어줬으므로 6번의 dequeue를 하는 식으로 구현했다.

 

그리고 K번의 swap을 했다면, 마지막에는 K stage에서 enqueue한 숫자들을 dequeue하면서 최댓값을 구한 다음 그 값을 출력하면 끝난다.

 

사실 알고리즘을 말로 설명해서 그렇지,

BFS로 완전 탐색을 하면 반드시 답을 구할 수 있다는 전제 하에서

반드시 K번 swap을 해야 하기 때문에 K 단계의 swap을 거치는 과정에서 중간에 어떤 값을 만나던 상관 없이 swap을 해야하고,

단지 경우의 수를 줄이기 위해 각 stage에서 중복을 제거하면 된다는 것만 알면 끝이다.

 

 

시간 복잡도

O({M(M-1)/2)^K) 보단 작은데 얼마나 작은지 모르겠다.

채점 기준 240ms 정도 나왔다.

 

 

공간 복잡도

K번째 단계에서 HashSet과 Queue에 들어가는 길이 M의 String의 개수만큼 메모리가 필요하다.

 

 

풀면서 놓쳤던 점

이 문제를 완전탐색을 하지 않아도 풀 수 있는 문제라고 생각했다.

 

K가 충분히 주어진다면, 주어진 숫자의 각 자리수를 내림차순 정렬한 숫자가 최댓값임은 자명하므로,

주어진 K번의 swap 기회에서 가장 높은 자리수에 가장 큰 숫자가 오게끔 마치 sorting을 하듯 swap을 먼저 하고,

K번 안에 내림차순 정렬을 하지 못하면 그 값을 그대로 정답으로 출력했다.

 

만약 K번 이내에 내림차순 정렬을 다 했는데, 반드시 K번 swap을 해야하므로

1. 남은 swap 횟수가 짝수이면, 같은 두 숫자를 짝수번 swap하면 그대로이므로 그냥 정답으로 출력

2. 남은 swap 횟수가 홀수이면 가장 낮은 자리수의 두 숫자를 swap한 뒤 정답으로 출력 (가능한 두번째로 큰 수가 된다)

 

위와같은 알고리즘을 적용했으나 실패했다.

 

그 이유는

K번 이내에 내림차순 정렬을 다 한 경우의 알고리즘에는 문제가 없으나,

K번 안에 내림차순 정렬을 못 한 경우에 문제가 있기 때문이다.

 

K번 안에 내림차순 정렬을 다 못한 경우는 사실상 selection sort를 중간에 멈춘 것인데,

이 때 selection sort는 K번째 값 까지가 정렬되어 있는 값임을 보장하지만 그 이후의 값은 정렬된 값임을 보장하지 않는다.

이 사실을 놓치고 그대로 풀다가 틀려버렸다.

 

입력이 31299 2 로 들어온 경우를 생각해보면 위 알고리즘이 왜 틀렸는지 알 수 있다.

참고 링크: https://www.acmicpc.net/board/view/62585

글 읽기 - Python 그리디로 풀어봤는데 반례좀 부탁드립니다.

 

 

이 문제에서 얻어갈 점

BFS의 응용.

BFS의 각 단계를 어떻게 구분할지, 그리고 각 단계마다 최적화를 어떻게 할 수 있는지에 대해 깊게 생각해 볼 수 있었다.

 

 

코드

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int num, numOfSwap;
        num = sc.nextInt();
        numOfSwap = sc.nextInt();

        //입력받은 수가 swap이 가능한 숫자인지 체크
        if (!canSwap(num))
        {
            System.out.println(-1);
            return;
        }

        //매 stage마다 겹치는 숫자가 있는지 체크하기 위한 HashSet
        HashSet<String> hs = new HashSet<>();

        //BFS를 위한 queue. swap을 편하게 하기 위해 String 형태로 처리한다.
        Queue<String> queue = new LinkedList<>();
        queue.add(Integer.toString(num));

        int curStagePivots = 1;
        int nextStagePivots = 1;
        String pivot;
        int max = -1;

        while (numOfSwap >= 0)
        {
            curStagePivots = nextStagePivots;
            nextStagePivots = 0;
            max = -1;

            //각 stage에서는 이전 stage에서 enqueue되었던 String만 처리해주면 된다
            for (int i = 0; i < curStagePivots; i ++)
            {
                pivot = queue.poll();

                //K번 swap을 했으면 최종적으로 swap한 String들을 하나씩 뽑으면서 최댓값을 구해줌
                if (numOfSwap == 0)
                    max = Math.max(max, Integer.parseInt(pivot));
                //이전 stage에서 enqueue했던 string을 swap해서 다시 queue에 넣어줌
                else
                    nextStagePivots += swapAndEnqueue(pivot, queue, hs);
            }

            //이전 stage에서 enqueue했던 string은 다음 stage에서 enqueue할 string에 영향을 주지 않음
            //왜냐하면 무조건 K번 swap을 해야만 하기 때문에 같은 stage에서 겹치는 것만 빼주면 되는거지
            //이전 stage에서 넣었다고 다음 stage에서 빼버리면 원하는 답이 안나온다!
            hs.clear();
            numOfSwap--;
        }

        System.out.println(max);
    }

    static int swapAndEnqueue(String pivot, Queue<String> queue, HashSet<String> hs)
    {
        String numSwapped;
        int enqueueCnt = 0;

        for (int i = 0; i < pivot.length() - 1; i++)
        {
            for (int j = i + 1; j < pivot.length(); j++)
            {
                numSwapped = swap(pivot, i, j);

                //이 stage에서 이미 넣었던 string인지 확인
                if (hs.contains(numSwapped))
                    continue;

                queue.add(numSwapped);
                enqueueCnt++;

                hs.add(numSwapped);
            }
        }

        //enqeue한 string 개수를 반환함
        return enqueueCnt;
    }

    static String swap(String str, int idx1, int idx2)
    {
        char[] result = str.toCharArray();
        result[idx1] = str.charAt(idx2);
        result[idx2] = str.charAt(idx1);

        return new String(result);
    }

    static boolean canSwap(int num)
    {
        //1,2,3,...,9
        if (num < 10)
            return false;

        //10,20,30,...,90
        if (num < 100 && num % 10 == 0)
            return false;

        return true;
    }
}