LeetCode 179. Largest Number

개발공부를해보자·2025년 2월 23일

LeetCode

목록 보기

61/95

파이썬 알고리즘 인터뷰 61번(리트코드 179) Largest Number
https://leetcode.com/problems/largest-number/

나의 풀이1

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        if not nums:
            return ""

        def custom_compare(s1, s2):
            if s1 + s2 > s2 + s1:
                return -1
            else:
                return 0

        nums = [str(x) for x in nums]
        nums.sort(key = cmp_to_key(custom_compare))
        result = str(int("".join(nums)))
        return result if result else ""

        # cmp_to_key에 대해 정리하자.

결론부터 말하면 'a'+'b' 와 'b'+'a' 중 누가 더 큰지 살펴보면 무엇을 앞에 쓸 지 알 수 있다.
24, 214를 생각해보자.
기본적으로 문자열 대소처럼 사전식 비교를 하여 큰 수부터 앞에 먼저 쓰면 된다. 24가 214보다 크니까(첫 번째 2 는 같고 두 번째 4 가 1 보다 크니까) 24 를 214 보다 먼저 쓰면 된다.
그런데 길이 짧은 수가 긴 수의 접두사인 경우 조금 더 생각해주어야 한다.
2, 20, 21, 22, 23, 24 를 생각해보자.
24→23→22→21→20 순서는 맞는데, 2 는 어디에 넣어야 할까? 22 의 앞이나 뒤에 넣어야 한다. 24→23→22→2→21→20 가 되는 것이다.
파이썬의 문자열 비교(사전식 비교)에서는 앞부터 따지다가 한쪽이 길이가 짧으면 길이 짧은 것을 작다고 판단한다.('2'<'21', '2'<'24')
하지만 지금은 '24'>'2'>'21'이 되어야 우리가 원하는 답이 나온다.
'24' 를 '2' 보다 먼저 써야하는 이유는 그렇게 했을 때 더 크기 때문이다. 그러니까 '24'+'2'>'2'+'24' 이기 때문이다.
마찬가지로 '2'+'21'>'21'+'2' 이므로 '2'를 '21' 보다 먼저 써야한다.
이를 이용하여 두 수 중 무엇이 큰 지 따질 수 있고, 두 수의 대소 관계가 정해진다면 전체를 정렬할 수 있다.

나의 풀이2(가독성 좋게 바꾼 것)

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = map(str, nums)

        nums = sorted(
            nums, key = cmp_to_key(lambda x, y: 1 if x + y < y + x else -1)
        )

        return str(int("".join(nums)))

나의 풀이3

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(x) for x in nums]
        nums.sort(key = lambda x: x *10)
        nums.reverse()
        return str(int("".join(nums)))

사실 이 방법으로 먼저 접근했다가 못 풀고 풀이1로 풀었었다.
그런데 문제를 다시 읽어보니 0 <= nums[i] <= 10^9 조건이 있었고 이 접근을 완성하여 풀 수 있었다.
아이디어는, '91', '9' 중 누가 앞에 와야 하는 지(큰 지) 생각해보자.
길이가 1칸 차이 난다. 짧은 녀석에 '9'를 이어 써주면 '91', '99'의 비교로 바꾸어 생각하여 '99'를 먼저 쓰면 되는 것을 알 수 있다.
'111311', '1113' 중 누가 앞에 와야 하는 지(큰 지) 생각해보자.
마찬 가지로 길이가 2칸 차이가 난다. 짧은 녀석에 '11'을 추가하여 '111311', '11311'로 바꾸면 이번에 같아지는데 이는 올바른 결과가 아니다. 그런데 4칸을 추가한다면 자기 자신인 '1113'을 한 번 더 반복해서 '11131113'이 된다. 즉 두 번 연달아 자신을 쓴 것이고 이번엔 오히려 길기 때문에 긴 것 '111311' 도 두 번 연달아 쓰면 '111311111311'이 된다. 두 번 연달아 쓴 것끼리 비교하면 대소를 알 수 있다.
그런데 각 수는 10^9 보다 작으므로 10번 연달아 쓰면 길이가 짧은 것을 염려하지 않고 대소 비교를 할 수 있다.

다른 풀이

class Solution:
    @staticmethod
    def to_swap(n1, n2):
        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))))