670. Maximum Swap

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

Maximum Swap - LeetCode

 

 특정 숫자가 주어지고, 최대 한 번의 digit간의 swap이 허용될 때 해당 swap을 사용하여 최대값을 만드는 문제다.

 

class Solution {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        
        int maxIdx = -1;
        int maxv = -1;
        int leftIdx = -1;
        int rightIdx = -1;
        
        for(int i = s.size() - 1; i >= 0; i--){
            if(maxv < s[i] - '0'){
                maxv = s[i] - '0';
                maxIdx = i;
                continue;
            }
            
            if(s[i] - '0' < maxv){
                leftIdx = i;
                rightIdx = maxIdx;
            }
        }
        
        if(leftIdx != -1)
            swap(s[leftIdx], s[rightIdx]);
        
        return stoi(s);
    }
};

 

 도형의 높이를 숫자의 값이라고 가정한다.  높은 자릿수와 낮은 자릿수를 swap해야 최댓값을 만들 수 있으므로 오른쪽부터 낮은 자릿수를 탐색한다.  부분 최댓값이 나왔을때 저장하고, 부분 최댓값보다 작은 값이 나왔을 때 leftIdx와 rightIdx를 각각 i(current idx), maxIdx로 초기화한다.  이러한 과정을 반복하는 도중 부분 최댓값보다 큰 값을 만난다.  이때, 부분 최댓값과 최댓값 인덱스만 수정하고 continue한다.  이유는 업데이트된 최댓값 이후에 해당 값보다 낮은 값이 나와야 swap을 할 수 있는데, 최댓값만 존재하는 경우는 swap할 수 없으므로 leftIdx와 rightIdx는 건들지 않는다.