LeetCode: 179. Largest Number

프로그래머스에도 있는 문제이다.

문제를 처음 봤을 때, 가장 먼저 nums를 정렬해야된다는 것을 알 것이다.

여기서 정렬을 어떻게 하는지가 핵심인데,

34343 과 3434 중 어느것이 먼저 나와야할지를 생각해보면 된다.

그냥 정렬한다면, 34343이 앞에 와버리는 문제가 있다.

34343+3434

반대의 경우는,

3434+34343

그러나 후자의 경우가 더 크다.

이를 검출할 수 있는 방법은 해당 숫자들을 반복시켜서 얻는 새로운 숫자열을 비교하는 것이다.

3434334343과 34343434 를 비교하면 된다.

아래 코드에서는 숫자를 10번 반복시키는데, 이는 숫자의 최대 길이가 10이기 때문이다. (1과 10000000000의 비교하는 경우)

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