61. Largest Number

🎯 leetcode - 179. Largest Number

---

📌 문제

- 파이썬 알고리즘 인터뷰 61번 문제

📌 날짜

2020.02.27

📌 시도 횟수

Failed

💡 Code

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def swap(left, right):
            return str(left) + str(right) < str(right) + str(left)

        cur = 0
        while cur < len(nums):
            comp = cur
            while comp > 0 and swap(nums[comp - 1], nums[comp]):
                nums[comp - 1], nums[comp] = nums[comp], nums[comp - 1]
                comp -= 1
            cur += 1
        return str(int("".join(map(str, nums))))

💡 문제 해결 방법

⭐ 삽입 정렬 + 자릿수 정렬 ⭐
1. 기본 틀은 삽입 정렬의 구조를 따른다.
- 현재 숫자와 인접한 숫자를 비교해서 스왑한다.
- 가장 처음으로 스왑되지 않을 때, 그 위치가 현재 숫자가 삽입될 위치이다.
2. 자릿수 정렬
- 예를 들어 9, 30이 있다고 가정하자. 자릿수 정렬에서는 9 > 30이다.
이것은 9, 30에 대하여 930 > 309 임을 활용해 자릿수 정렬을 할 수 있다.
즉, 숫자 a, b가 있을 때 a+b, b+a를 비교해서 자릿수 정렬을 한다.
- 해당 문제에서는 인접한 숫자를 left로, 현재 숫자를 right라고 가정했을 떄
(left+right) < (right+left) 이면 두 숫자를 swap 한다.


ex. [3, 30, 34, 5, 9]가 있다고 할때, 각 단계마다 어떻게 스왑되는지 보면서 이해해보자.
------------------
[3, 34, 30, 5, 9]	=> (현재 3 의 위치 찾는 중)
[34, 3, 30, 5, 9]	=> (현재 34의 위치 찾는 중) 334 < 343 이므로 3 <-> 34 스왑
[34, 3, 5, 30, 9]	=> (현재 5 의 위치 찾는 중) 35 < 53 이므로 3 <-> 5
[34, 5, 3, 30, 9]	=> (현재 5 의 위치 찾는 중) 345 < 534이므로 swap
[5, 34, 3, 30, 9]	=> (현재 30의 위치 찾는 중) 
[5, 34, 3, 9, 30]	=> (현재 9 의 위치 찾는 중) 309 < 930이므로 swap
[5, 34, 9, 3, 30]	=> (현재 9 의 위치 찾는 중) 39 < 93이므로 swap
[5, 9, 34, 3, 30]	=> (현재 9 의 위치 찾는 중) 349 < 934이므로 swap
[9, 5, 34, 3, 30]	=> (현재 9 의 위치 찾는 중) 59 < 95이므로 swap
------------------
✔ 최종 결과 : 9534330

• 각 단계별로 그림을 그려 이해해보자. 언제 swap 되는지에 주목하자.
  

💡 새롭게 알게 된 점

⭐ 자릿수 단위로 비교하는 정렬을 하는 방법
>> str(num1) < str(num2)
와 같이 str으로 바꾸면 파이썬에서 자릿수 단위를 우선순위로 하여 비교할 수 있다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 2개씩 자릿수 비교를 통해 정렬할 수 있음을 파악하기 어려웠다.

---