[leetcode 2024/02/22] 179. Largest Number

https://leetcode.com/problems/largest-number/description/

Largest Number - LeetCode

 

1. 접근 방법

문자열의 아래와 같은 특성을 이해하고 문제를 접근하는 것이 좋다.

test_list = ['10', '9']
test_list.sort()
print(test_list)

## 출력: ['10', '9']

 

이렇게 int로 형 변환을 하지 않고 숫자를 비교하게 되면 앞에서 부터 차례로 비교하게 된다.

즉, 1 vs 9 로 비교하고 1이 작으니, 10 을 더 작은 순으로 판단 먼저 출력하게 된다. ( reverse가 아닌 경우 )

 

이러한 특성 덕분에 sort(reverse = True)를 하게 된다면, 

['9', '10'] 으로 정렬이 되어 순서대로 문자열에 넣어 출력하면 된다. -> 910

 

하지만 주의해야할 점이 있다. 

 

'30' 와 '3' 을 비교할 경우, [ '30', '3'] 으로 출력이 되게 된다. 즉 3 뒤에 0 이 있는 30과 3 뒤에 아무 값이 없는 0 중에서, 

30을 더 크다고 판단. 30을 먼저 출력하게 되는 것이다.

그렇게 된다면 : 303 을 반환하게 되고, 틀리게 되는 것이다. (330이 더 큰 수이기 때문)

이에 대한 것을 아래의 출력 결과로 확인할 수 있다.

str_nums = list(map(str, nums))
sorted_1 = sorted(str_nums, reverse=True)

# 출력 결과 : ['9', '5', '34', '30', '3']

 

3을 30보다 앞에 오게 ( 더 크게 판단 ) 하기 위해서는 어떻게 해야할까?

 

Constraints 의 조건을 확인해보자.

0 <= nums[i] <= 10**9 임을 알 수 있다. 

즉 숫자가 10자리를 넘어가지 않음을 확인할 수 있다.

 

아래와 같이 * 10을 하게 된다면, 다음과 같은 출력 결과를 얻을 수 있다.

print('3' * 10)
print('30' * 10)

# 출력 결과 : 3333333333
#           30303030303030303030

 

이렇게 곱하기 10을 통해 자리수를 10까지 키워주면 된다.

 

이를 key로 비교하게 된다면 3이 30보다 더 크다고 판단, List의 앞 부분에 위치하게 될 것이다.

3과 30을 비교하는 경우 *2를 해도 충분히 3이 앞에 있다고 판단할 수 있다.

33 vs 3030 이면, 두 번째 숫자에서 3 > 0 이기 때문에 3이 앞에 있다고 판단될 것이다.

 

하지만 9자리까지 수가 차 있게 된다면, 3에 10을 곱해줘야 비로소 가능해지기 때문이다. (사실 9의 자리수까지 가능하기 때문에, 9 만 곱해줘도 충분하다)

 

print('3' * 10)
print('333333331' * 10)

# 출력 결과 : 3333333333
#         : 333333331333333331333333331333333331333333331333333331333333331333333331333333331333333331

 

이런식으로 확인해줄 수 있다.

 

하지만, 두 번째 출력이 너무 불필요하게 길게 느껴질 수 있다.

미리 숫자의 최대 길이와 최소 길이를 알아낸다면 딱 필요한 만큼 expand를 할 수 있다.

 

66와 

666661 가 있다고 가정하고, 각각 최소 길이, 최대 길이 라고 해보자

 

66 -> len: 2

666661 -> len: 6 이다.

66에 곱하기 3 [ max_len / min_len ]만 한다면, 666666 -> len: 6 인 수가 나오게 되므로 적합한 비교를 할 수 있게 된다.

max_len/min_len을 하게 되면 소수점이 생길 수 있기 때문에 잊지 말고 올림을 해줘야 한다. [ math.ceil ]

 

 

여기서 더 들어가면, 모든 숫자의 길이를 최대의 길이까지 맞게 확장시킬 수 있다. 

즉, 

1

22

6666이 있다고 가정할 때, 

1111

2222

6666 

이런식으로 확장시켜 비교하는 것이다. 하지만 각각의 숫자의 길이와 최대 길이를 비교해서 확장하는 과정이 필요하기 때문에,

배 보다 배꼽이 더 큰 경우가 발생할 것이다.

 

따라서 여기서 만족하고 멈추도록 하겠다.

코드로는 1) 10을 곱하는 코드 2) max_len / min_len 만큼 곱한 코드 2개를 넣어볼 것이다.

 

2. 코드

1) multiply 10

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        str_nums = map(str, nums)
        sorted_nums = sorted(str_nums, key = lambda x: x*10, reverse = True)
        connected_str = ''
        for s in sorted_nums:
            connected_str += s
        return '0'if sum(nums) == 0 else connected_str

 

2) max_len / min_len

import math

class Solution:
    def suitable_length(self, nums):
        max_len = len(str(max(nums)))
        min_len = len(str(min(nums)))
        suitable_len = math.ceil(max_len/min_len)
        return suitable_len

    def largestNumber(self, nums: List[int]) -> str:
        
        suitable_len = self.suitable_length(nums)
        str_nums = map(str, nums)

        sorted_nums = sorted(str_nums, key = lambda x: x * suitable_len, reverse = True)
        connected_str = ''
        for s in sorted_nums:
            connected_str += s
        return '0'if sum(nums) == 0 else connected_str