[Algorithm] LeetCode 670. Maximum Swap (java)

풀이 코드

class Solution {

    public int maximumSwap(int num) {
        char[] numArr = Integer.toString(num).toCharArray();
        int n = numArr.length;
        int[] maxRightIndex = new int[n];

        maxRightIndex[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; --i) {
            maxRightIndex[i] = (numArr[i] > numArr[maxRightIndex[i + 1]])
                ? i
                : maxRightIndex[i + 1];
        }

        for (int i = 0; i < n; ++i) {
            if (numArr[i] < numArr[maxRightIndex[i]]) {
                char temp = numArr[i];
                numArr[i] = numArr[maxRightIndex[i]];
                numArr[maxRightIndex[i]] = temp;
                return Integer.parseInt(new String(numArr));
            }
        }

        return num;
    }
}

 

 

사고 과정

 

https://leetcode.com/problems/maximum-swap/

 

문제에서 요구하는 것은 단 하나. 

주어진 int형 num에서 임의의 두 수를 "한 번만"swap하여 최대의 숫자가 나오도록 하여라. 

 

알고리즘 시작~!

Solution 1. Brute-Force

 

우선 서로 다른 자리의 숫자를 swap해야하므로, int형 변수 num을 char[] 배열로 바꾸리란 생각은 자연스레 들 것이다. 

 

그렇다면, 이중 for문으로 char[] 배열 내의 element 중 두 수를 골라 swap하는 모든 경우의 수를 구하고, 이 중 최대값을 출력하면 되는게 아닌가? 

 

이를 정직하게 구현한 코드는 다음과 같다. 

 

class Solution {

    public int maximumSwap(int num) {
        String numStr = Integer.toString(num); 
        int n = numStr.length();
        int maxNum = num; 

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                char[] numArr = numStr.toCharArray(); 
                char temp = numArr[i];
                numArr[i] = numArr[j];
                numArr[j] = temp;

                int tempNum = Integer.parseInt(new String(numArr)); 

                maxNum = Math.max(maxNum, tempNum); 
            }
        }

        return maxNum; 
    }
}

 

직관적이고 정직한 풀이지만, 시간 복잡도가 O(n^2)라는 점에서 문제를 풀고도 찝찝한 감을 버릴 수가 없다. 

 

조금 더 시간 효율적인 풀이가 없을까? 

 

Solution 2. Greedy

문제를 유심히 살펴보자. 

 

문제에서는 숫자 두 개를 "한 번만" swap하여 최대 숫자를 만들 것을 요구하고 있다. 

 

단순히 최대 숫자가 되도록 swap하라는(이 경우에는 단순 정렬 문제가 되겠지만,) 것이 아닌, 한 번만 swap했을 때 가능한 최대의 숫자가 나오도록 요구하고 있는 것이다. 

 

그렇다면, 가장 큰 수가 가장 높은 자리수에 갈 수 있도록 swap해주면 되는 것이 아닌가? 

 

결국, 각 자리 기준 오른쪽의 숫자 중 가장 큰 수의 index를 임의의 int 배열에 저장해두고, 
이 가장 큰 수가 가장 큰 자릿수에 올 수 있도록 해주면 될 것 같다. 

 

이를 코드로 구현하면 다음과 같다. 

 

class Solution {

    public int maximumSwap(int num) {
        char[] numArr = Integer.toString(num).toCharArray();
        int n = numArr.length;
        int[] maxRightIndex = new int[n];

        maxRightIndex[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; --i) {
            maxRightIndex[i] = (numArr[i] > numArr[maxRightIndex[i + 1]]) ? i : maxRightIndex[i + 1];
        }

        for (int i = 0; i < n; ++i) {
            if (numArr[i] < numArr[maxRightIndex[i]]) {
                char temp = numArr[i];
                numArr[i] = numArr[maxRightIndex[i]];
                numArr[maxRightIndex[i]] = temp;
                return Integer.parseInt(new String(numArr));
            }
        }

        return num;
    }
}

 

처음에는 막막했는데, 조금 생각해보니 의외로 간단히 풀렸던 문제