[LeetCode] 670. Maximum Swap

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

leetcode - Maximum Swap

문제 유형: 그리디, 수학

문제 난이도: Medium

 

문제

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

 

정수 num을 입력받습니다. 자릿수에서 두 개의 숫자를 바꿔서 최대값의 숫자로 변환할 수 있습니다.

얻을 수 있는 최대값의 숫자를 출력하시오.

 

풀이

브루트 포스 방법과, 인덱스를 이용한 방법이 있다.

브루트 포스로는, 자릿수마다 다 한 번씩 스왑해보면서 최대 값을 구해보는 방법이 있다.

 

인덱스를 이용하는 방법은, 좀 트리키할 수 있다.

last라는 배열을 만들어서, last[i] = 마지막으로 숫자 i가 등장한 인덱스를 나타낸다.

 

그 뒤, 가장 높은 자릿수가 9부터 자기자신+1 까지 찾아보면서, 자신보다 큰 숫자들 중에서 자신의 인덱스보다 늦게 나온 숫자를 하나 찾는다.

그리고, 그 숫자와 바꾸고 반환해주면 된다.

스왑은 한 번만 되므로, 앞쪽자릿수의 입장에서는, 자신보다 최대한 큰 수이면서, 최대한 맨 뒤에 있는 인덱스와 교환하는 것이 가장 최적이다.

 

코드

C++

class Solution {
public:
    int maximumSwap(int num) {
        vector<int> last(10, -1);
        string digits = to_string(num);
        int n = digits.size();

        for(int i = 0; i < n; ++i) {
            last[digits[i] - '0'] = i;
        }

        for(int i = 0; i < n; ++i) {
            for(int d = 9; d > digits[i] - '0'; --d) {
                if(last[d] > i) {
                    swap(digits[i], digits[last[d]]);
                    return stoi(digits);
                }
            }
        } 
        return num;
    }
};