[알고리즘] 가장 큰 수

가장 큰 수

책 풀이

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

        print(nums)
        return str(int(''.join(map(str, nums))))

처음에는 리스트를 역순으로 정렬하여 element들을 붙이면 된다고 생각했다. 하지만 리스트가 [3, 30, 34, 5, 9]일 때 정렬하면 [9, 5, 34, 30, 3]이 나온다. 가장 큰 값은 [9, 5, 34, 3, 30] 일때 나온다. String은 사전순으로 앞글자씩 비교하지만, "3"과 "30"같은 경우 "30"은 뒤에 한 글자가 더 있으므로 30이 더 크다고 나온다. 두 개씩 비교하여 정렬을 해야하는데 그 기준은 a와 b가 있을 때 a+b 와 b+a를 비교하는 것이다.