[LeetCode] 670: Maximum Swap

문제

문제 링크 : 670: Maximum Swap

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.

 

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

 

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap.

 

Constraints:

• 0 <= num <= 10^8

풀이

class Solution {
public:
    int maximumSwap(int num) {
        int arr[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
        int len=0;
        while(num>0){
            arr[len++] = num%10;
            num/=10;
        }

       

        for(int i=len-1; i>=0; i--){
            int max = 0, maxi = 0;
            for(int j=i-1; j>=0;j--){
                if(max <= arr[j]){
                    max = arr[j];
                    maxi = j;
                }
            }
            if(max > arr[i]){
                arr[maxi] = arr[i];
                arr[i] = max;
                break;
            }
        }

        int ans = 0;
        for(int i=len-1; i>=0; i--){
            ans*=10;
            ans+=arr[i];
        }
        return ans;

    }
};

 

선택정렬 알고리즘에서 아이디어를 얻어 최초 swap이 이루어지면 종료하도록 했다.

제출