Table of Contents
가장 큰 수
난이도 | ★★
리트코드 179
문제
GivGiven a list of non-negative integers nums, arrange them such that they form the largest number.
Note: The result may be very large, so you need to return a string instead of an integer.
Example 1:
Input: nums = [10,2]
Output: "210"
Example 2:
Input: nums = [3,30,34,5,9]
Output: "9534330"
Example 3:
Input: nums = [1]
Output: "1"
Example 4:
Input: nums = [10]
Output: "10
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 109
[전제]
class Solution:
def largestNumber(self, nums: List[int]) -> str:
문제 풀기 전 알고 갈 개념
풀이
각 요소 단위로 크기 순으로 정렬하면 된다.
단, 맨 앞에서부터 자릿수 단위로 비교해서 크기 순으로 정렬한다.
정렬을 위한 도구 함수 세팅
이를 위해 여기선 특별한 비교 함수를 만들어 보겠다!!
def to_swap(n1: int, n2: int) -> bool:
return str(n1) + str(n2) < str(n2) + str(n1)
ex) 9 와 30 비교
위 함수를 조건으로 추가한 정렬
- 위의 boolen 함수가 True일 경우, 즉 두 숫자의 자리를 바꿔야 할 경우를 찾아 바꿔준다
def largestNumber(self, nums: List[int]) -> str:
i = 1
while i < len(nums):
j = i
while j > 0 and self.to_swap(nums[j - 1], nums[j]):
nums[j], nums[j - 1] = nums[j - 1], nums[j]
j -= 1
i += 1
return str(int(''.join(map(str, nums))))
[잘 안보이시는 분들을 위해] 
+ 마지막 리턴값
원래 ‘‘.join(map(str, nums)) 정도면 끝나게 되겠지만,
여기서는 입력값이 [“0”,”0”] 인 경우도 있기 때문에 그냥 문자로 처리해 버리면 리턴값이 00 이 됨
➡ join() 결과를 int 로 바꿔서 00 이 0 이 되도록 만들어 준 후, 다시 str 로 변경해서 그런 일이 없게 함
전체 코드
class Solution:
@staticmethod
def to_swap(n1: int, n2: int) -> bool:
return str(n1) + str(n2) < str(n2) + str(n1)
def largestNumber(self, nums: List[int]) -> str:
i = 1
while i < len(nums):
j = i
while j > 0 and self.to_swap(nums[j - 1], nums[j]):
nums[j], nums[j - 1] = nums[j - 1], nums[j]
j -= 1
i += 1
return str(int(''.join(map(str, nums))))