가장 작은 일련번호

문제

부품 상자마다 번호표가 하나씩 붙어 있고, 상자를 원하는 순서로 늘어놓은 뒤 번호표를 왼쪽부터 그대로 이어 적어 창고 일련번호를 만듭니다. 예를 들어 번호표가 4, 45, 7 이라면 4 45 7 순서로 놓아 "4457", 45 7 4 순서로 놓아 "4574" 를 만들 수 있습니다.

번호표 배열 parts 가 주어질 때, 이렇게 만들 수 있는 가장 작은 일련번호를 문자열로 반환하세요.

• 이어 붙인 결과의 맨 앞에 0 이 오면 그 0 들은 일련번호에 적지 않습니다. (예: "0790" 은 "790" 으로 적습니다.)
• 앞의 0 을 모두 지웠을 때 남는 것이 없다면 "0" 을 반환합니다.

solution(parts: number[]): string

예시

[30, 3] 은 "303" 과 "330" 두 가지가 가능하므로 "303" 이 답입니다. 번호표를 숫자 크기순으로 정렬하는 것만으로는 최솟값이 되지 않는다는 점에 주의하세요.

제약 조건

• 1 ≤ parts.length ≤ 100,000
• 0 ≤ parts[i] ≤ 10,000
• 반환값은 문자열입니다 (매우 길어질 수 있어 숫자 타입으로는 표현할 수 없습니다)

시간 복잡도 목표: O(N log N)