가장 큰 수 (lv2)

문제 설명

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

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

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

 

제한 사항

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

---

 좀... 흥미로운 문제다. 문제의 핵심은 각 수들의 "우선순위"를 파악하는 것인데, 사견이지만 쉽게 눈치채기는 어려운 부분이라고 생각한다. 예를 들면 [101, 10, 232, 23] 로 가장 큰 수를 만들어보자. 아무래도 앞의 두 수는 1로 시작하는 만큼 먼저 가져오면 안될거라는 생각이 들고, 뒤의 두 수 중 하나를 골라야 할 것이다. 그런데 뒤의 두 수는 첫 자리가 2로 같다. 둘 중 어떤게 더 큰 수를 만들 때 유리할까? 232를 먼저 골랐을 때, 뒤에 무조건 세 자리수가 채워져야 한다고 가정해보자. 규칙이 어떻든 간 232가 가장 앞에 와있으니 그 뒤는 어떻게든 각 자리가 232보다 같거나 작은 수로 채워져야 할 것이다. 예를들면 232232는 괜찮지만, 232233은 안된다. 애초에 233이 있었거나, 아니면 23과 3이 있었거나 했으면 3을 앞으로 가져와 더 큰 수를 만들 수 있었을 것이다. 여기서 힌트를 얻자면, 그럼 각 숫자를 세 자리수까지 수를 반복하면서 꽉 채운뒤 값을 비교하면 되지 않겠느냐, 라는 말이다. 아래 코드는 그와 같은 방법으로 문제를 풀이하는데, 파이썬에서 문자열 비교는 첫 인덱스부터 차례대로 비교한다는 점을 고려해서 보면 된다. 예를 들면 '2323'과 '232232' 가 있으면 첫 자리인 2부터 차례대로 비교해나가다 넷째자리에 와서 3이 2보다 크니 '2323'이 '232232'보다 크다고 출력되는 것이다.

코드

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