[코테] 리트코드 정렬 179. Largest Number

179. Largest Number

문제 링크

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

문제 설명

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Since the result may be very large, so you need to return a string instead of an integer.

제한 사항

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

입출력 예 #1

1. Input : nums = [10,2]
2. Output : “210”

입출력 예 #2

1. Input : nums = [3,30,34,5,9]
2. Output : “9534330”

문제 풀이

배열의 2개 항목씩 꺼내서 string 타입으로 합쳤을 때 앞에 항목이 뒤에 항목보다 클 경우 swap하여 정렬한다.

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))))