[LeetCode] 670. Maximum Swap

LeetCode - 670. Maximum Swap 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/maximum-swap/

풀이

음이 아닌 정수가 주어질 때 숫자의 두 자리를 한 번만 바꾸어 최댓값이 되도록 만드는 문제이다.

현재 자릿수(위치)를 기준으로 나머지 자릿수와 값을 바꾸어 보면서 최댓값을 구하고 반환하였다.

stoi함수는 string을 int로 변환하는 함수로서 "1234"를 1234로 바꾸어 주며, 앞자리에 0이 들어있는 경우는 0을 무시한 나머지 숫자를 int로 변환한다. ("0001234" → 1234)

• 만약 숫자의 자리를 바꾸는데 제한이 없고 주어진 숫자로 만들 수 있는 최댓값을 만드는 문제였다면 0~9 값에 대한 계수 정렬(counting sort)을 활용하여 풀 수 있다.

소스 코드

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        int maxV = num;
        for (int i = 0; i < s.length(); ++i) {
            for (int j = i + 1; j < s.length(); ++j) {
                swap(s[i], s[j]);
                int temp = stoi(s);
                if (maxV < temp) {
                    maxV = temp;
                }
                swap(s[i], s[j]); // swap restore
            }
        }
        return maxV;
    }
};