Maximum Swap[Math,Greedy]

https://leetcode.com/problems/maximum-swap/description/?envType=daily-question&envId=2024-10-17

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 <= 108

오늘의 코딩문제~ 난이도는 Medium인데, description이 짧아서 좋다.

 

함 머리좀 굴려볼까나~

 

1. Python

class Solution:
    def maximumSwap(self, num: int) -> int:
        lst = []
        while num>0 :
            lst.insert(0,num%10)
            num//=10
        # if len(lst)==1 : return lst[0] # 1ea case

        for i in range(len(lst)-1): # consider last idx!
            if lst[i] < max(lst[i+1:]) :
                # Swap with max val, at very last part of the lst
                temp = max(lst[i+1:])
                for j in range(len(lst)-1,i,-1):
                    if lst[j]==temp:
                        lst[i],lst[j] = lst[j],lst[i]
                        break
                break
        ans = 0
        cnt = len(lst)-1
        for x in lst:
            ans += x*(10**cnt)
            cnt-=1
        return ans

 

나는 약간 C? 스럽게 파이썬 코드를 짰는데, Python의 여러 method를 사용하면 아래처럼 깔끔하게도 표현 가능 ㅎㅎ;;

메카니즘은 똑같은데 가독성이 아래가 훨씬 좋다!

class Solution:
    def maximumSwap(self, num: int) -> int:
        s = list(str(num))
        for i in range(len(s) - 1):
            max = (s[i], i)
            for j in range(i + 1, len(s)):
                if s[j] >= max[0]:
                    max = (s[j], j)
            if max[0] > s[i]:
                s[i], s[max[1]] = s[max[1]], s[i]
                break
        return int("".join(s))

 

2. C

 

skip, 각종 method 구현 짜침;

max, swap 등...

 

3. C++

class Solution {
public:
    int maximumSwap(int num) {
        string str = to_string(num);
        int n = str.size();
        vector<int> vec;
        // save it to the container
        for(char x : str) vec.push_back(x-'0');
        bool cond = false;
        int temp;
        for(int i=0;i<n;i++){
            temp = i;
            for(int j=n-1;j>i;j--){
                if(vec[j]>vec[temp]){
                    temp = j;
                    cond = true;
                }
            }
            if(cond){
                swap(vec[temp],vec[i]);
                break;
            }
        }
        int ans = 0;
        int cnt = n-1;
        for(int k=0;k<n;k++){
            ans += vec[k]*pow(10,cnt--);
        }
        return ans;
    }
};