670. Maximum Swap

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:01:44

 

---

 

문제 설명

 

 

정수 num을 입력으로 받는다. 단 한 번 두 자릿수를 교체할 수 있고, 이를 통해 가장 큰 숫자를 만들어야 한다.

 

얻을 수 있는 가장 큰 숫자를 반환하라.

---

 

풀이

 

우선, 문제 조건이 그렇게 빡빡하지 않아 브루트포스로 풀린다. 단순히 모든 경우를 테스트해서 가장 큰 숫자를 반환하면 된다.

 

풀이 코드(브루트포스)

class Solution:
    def maximumSwap(self, num: int) -> int:
        length = len(str(num))
        result = num
        for i in range(length-1) :
            ni = int(str(num)[i])
            for j in range(i+1, length) :
                nj = int(str(num)[j])
                tmp = num - ni * 10 ** (length - i - 1) - nj * 10 ** (length - j - 1)
                tmp = tmp + ni * 10 ** (length - j - 1) + nj * 10 ** (length - i - 1)
                result = max(result, tmp)
        return result

 

 

 

 

...보다싶이, 브루트포스로 풀면 성능이 매우 좋지 않다. 코드 문제 풀이에서 O(N^2)은 대부분 그렇게 효율적인 시간복잡도는 아니다. 

 

좀 더 세련된 풀이를 찾던 와중, 결국 솔루션 부분을 건드렸다.

 

잘 생각해보면, 다음 규칙을 따르기만 하면 된다.

• 제일 높은 자릿수부터 탐색한다(높은 자리 숫자가 클수록 더 큰 숫자이므로)
• 현재 자릿수 숫자 오른쪽에 있는 숫자들 중
  • 현재 자릿수 숫자보다 크면서 제일 숫자가 크고 (9, 8, 7...)
  • 그러한 숫자가 많다면 제일 오른쪽에 있는 숫자(동일한 숫자라면 제일 낮은 자릿수 숫자를 교환하는게 더 결과가 크다)
• 를 교환하기만 하면 된다.

시간복잡도는 무조건 O(N)이 된다.

 

풀이 코드

class Solution:
    def maximumSwap(self, num: int) -> int:
        num_list = list(str(num))
        last = {int(n) : i for i, n in enumerate(num_list)}
        print(last)
        for i in range(len(num_list)) :
            n = int(num_list[i])
            for j in range(9, n, -1) :
                if j in last and last[j] > i :
                    num_list[last[j]] = str(n)
                    num_list[i] = str(j)
                    return int(''.join(num_list)) 
        return num