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
💡 新知
⭐ 자릿수 단위로 비교하는 정렬을 하는 방법
>> str(num1) < str(num2)
와 같이 str으로 바꾸면 파이썬에서 자릿수 단위를 우선순위로 하여 비교할 수 있다.
答えを間違える理由
- 2개씩 자릿수 비교를 통해 정렬할 수 있음을 파악하기 어려웠다.
Reference
この問題について(61. Largest Number), 我々は、より多くの情報をここで見つけました https://velog.io/@eunseokim/61.-Largest-Numberテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol