문제

https://school.programmers.co.kr/learn/courses/30/lessons/42746
임의의 숫자 리스트가 주어졌을 때 숫자를 이어 붙여 만들 수 있는 가장 큰 수를 알아내야 한다.

풀이

문제를 보고 가장 먼저 생각난 것은 단순히 모든 순열을 만들고 가장 큰 수를 찾는 방법이였다. 하지만 숫자 리스트의 길이가 최대 100,000 이기 때문에 이는 필히 TLE가 발생할 것이다.

완전히 탐색하지 않고 가장 큰 수를 찾는 방법을 찾아야한다.
다음으로 떠오른 방법은 정렬을 이용하는 것이다.

가장 큰 수가 되야하는 조건을 생각해보자.

우선 자릿수가 가장 커야한다.
주어진 숫자들을 모두 이어붙인다면 어차피 자릿수는 다 똑같을 것이다.

그렇다면 0 ~ 9 까지의 수 중 가장 큰 수가 제일 앞에 위치하도록 해야한다. 즉 주어진 숫자들의 가장 맨 앞의 숫자를 기준으로 내림차순 정렬하여 이어 붙인다. 숫자들을 문자열로 바꾸고 내림차순 정렬 한다고 생각해보자

[3, 30, 34, 5, 9] -> [9, 5, 34, 30, 3]이 된다.
이는 9534303 인데 30 과 3의 위치를 바꾼다면 95434330으로 더 큰 수를 만들어낼 수 있다. 그래서 이 부분에 대해서 더 생각해봐야 한다.

문자열을 정렬할 때는 첫 글자부터 살펴보며 정렬을 한다. (첫글자 비교 후 두번 째 글자로 넘어가는 식) 미리 특정 횟수를 반복시킨 문자열끼리 비교시키면 어떻게 될까?
예를 들어 3 과 30 을 3번씩 반복시킨다면 333 과 303030이 될 것이다. 이를 내림차순으로 정렬한다면333 이 303030 보다 앞에 위치하게된다.
굳이 3번을 반복한 이유는 숫자의 크기가 1000이하로 제한되기 때문이다.

마지막으로 조심해야 할 점은 주어진 숫자들이 모두 0일 때이다.
모두 0이라면 '0'을 출력하도록 예외처리를 해주면 된다.

CODE

def solution(numbers):
    if sum(numbers) == 0: return '0'
    return ''.join(sorted([str(num) for num in numbers], key=lambda x: x*3, reverse=True))