179 Largest Number
179 Largest Number
문제
Given 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.
조건
- 1 $\le$ nums.length $\le$ 100
- 0 $\le$ nums[i] $\le 10^{9}$
예제
Input: nums = [10,2]
Output: "210"
Input: nums = [3,30,34,5,9]
Output: "9534330"
Input: nums = [1]
Output: "1"
Input: nums = [10]
Output: "10"
해결
1st
1 생각
num1 + num2와num2 + num1을 비교하여 더 큰 수가 되도록 정렬
1 코드
def largestNumber(self, nums: List[int]) -> str:
ans = ''
# 요소 단위로 크기 순으로 정렬
# 맨 앞에서부터 자릿수 단위로 비교해서 크기 순으로 정렬
i = 1
while i < len(nums):
j = i
while j > 0 and self.to_swap(nums[j - 1], nums[j]):
tmp = nums[j]
nums[j] = nums[j - 1]
nums[j - 1] = tmp
j -= 1
i += 1
return "0" if nums[0] == 0 else ''.join(map(str, nums)) # 첫 숫자가 0인 경우 "0" 반환
def to_swap(self, n1: int, n2: int) -> bool:
return str(n1) + str(n2) < str(n2) + str(n1)
2 리트코드 다른 풀이
2 코드
def largestNumber2(self, nums: List[int]) -> str:
nums.sort(key = lambda x: x/(10**len(str(x))-1), reverse=True)
return "0" if nums[0] == 0 else "".join(map(str,nums))
def largestNumber3(self, nums: List[int]) -> str:
def key_func(num):
denominator = (10 **len(str(num))) - 1 # 순환소수로 만들기 위한 분모값
# denominator = 10 **(len(str(num)) - 1) 이게 아니다!
key = num / denominator
print("largestNumber3: {} / {} to {}".format(num, denominator, key))
return key
nums = sorted(nums, key = key_func, reverse = True)
print(nums)
return "0" if nums[0] == 0 else "".join(map(str,nums))
- 아주 신박한 풀이다. 처음에는 숫자를 문자열로 바꾸고,
문자열 자리수 -1만큼 10을 거듭제곱하여 원래 수를 나눠서 유리수로 만든 후에 비교하는 건 줄 알았다
111311 / 100000 to 1.11311
1113 / 1000 to 1.113
[111311, 1113]
1113111113
- 하지만 그게 아니라,
문자열 자리수만큼 10을 거듭제곱하고 -1을 한 수로 수를 나눈다. 그럼 아래와 같이 나온다
111311 / 999999 to 0.11131111131111131
1113 / 9999 to 0.1113111311131113
[1113, 111311]
1113111311
- 결과를 놓고 보면,
1.113보다1.11311가 크므로 역순 정렬 시1.11311가 앞으로 온다. 하지만 두 수를 문자열로 연결하면1113111113가 나오고1113111311보다 작게 된다
1113111113
1113111311
- 정수를
순환 소수(repeating decimal)로 바꿔서 비교.
1/9
0.1111111111111111
1/99
0.010101010101010102
1/999
0.001001001001001001
- 10진수 체계에서 9는 3이라는 2와 5가 아닌
소인수(prime factor)를 갖는다. 10진수 체계에서 3은 10을 나눌 수 없으므로, 어떤 숫자를 9로 나눈다면 반복해서 나누게 된다. - 아래 내용 참조