[프로그래머스] 가장 큰 수

문제 분류

• 정렬

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

사고 과정

1. 큰 수 부터 오는게 낫지 않을까? → No
   • [10, 2]의 경우 → ‘102’보다 ‘210’이 더 크기 때문에 안됌
2. 앞자리가 큰 수부터 오면 되지 않을까? → Yes…But?
   • [3, 30, 31, 32, 33, 34]의 경우 → 우선순위를 어떻게?
3. “크게 만드는 수의 기준” - 정렬 기준
   1. 길이가 같다면 큰 수가 앞에 오는게 유리
   2. 길이가 다르면 다른 기준이 필요함.

알고리즘

1. 각 수를 문자열로 변환한다. 파이썬에선 숫자 형태의 문자열에 대한 sorting도 잘 수행된다.
2. 각 수를 정렬하되, 문자열을 반복 형태로 padding하고 4자리에서 끊어준다.
3. 각 수를 병합하고 정답을 출력한다.
4. 만약 첫번째 자리가 0인 경우, ‘000・・・’ 꼴이므로 ‘0’을 출력한다.

복잡도 분석

스트링 변환이나 병합 과정에서는 $O(n)$만큼의 복잡도가 사용된다.

정렬하는 과정에서 $O(nlogn)$만큼의 시간이 소요된다.

풀이

def solution(numbers):
    n = list(map(str, numbers))
    s = sorted(n, reverse=True, key=lambda x: (x * 4)[:4])
    a = ''.join(s)
    return '0' if a[0] == '0' else a