[Programmers/Python] 정렬 - 가장 큰 수

Programmers - 가장 큰 수

문제

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. sort를 이용하되, 조건을 잘 생각해 볼 문제
2. 우선 numbers의 요소들을 map 함수를 이용해 문자열로 변환한다.
3. 변환한 문자열을 내림차순으로 정렬한다.
   이때, 문자열이므로 '사전순'으로 정렬하게 되며, 예제 2의 경우 '['9', '5', '34', '304', '30', '3']'으로 정렬된다.
   문제 조건에서 number의 원소가 1,000 이하라고 하였으므로 각 원소에 3을 곱하여 '['333', '303030', '343434', '304304304', '555', '999']' 형태로 만든 뒤 정렬하면 '['999', '555', '343434', '333', '304304304', '303030']'와 같이 정렬되는 것을 확인할 수 있다.
   즉 정렬 조건(key)을 'lambda x: x*3'과 같이 설정하면 원하는 형태로 정렬이 이루어진다.
4. join을 이용해 numbers를 모두 결합하여 반환한다. 이때 결과가 [0, 0, 0, 0]인 경우도 있으므로 결괏값을 int로 변환한 후 다시 str로 바꾸어 반환한다(이 작업을 하지 않으면 0000으로 반환된다).

코드

def solution(numbers):
    numbers = sorted(list(map(str, numbers)), key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))