가장 큰 수

문제

0또는 양의 정수가 주어졌을때, 점수를 이어 붙여 만들 수 있는 가장 큰 수를 구하기

numbers배열이 주어질때 순서를 재배치하여 만들 수 있는 가장 큰수를 문자열로 바꾸어 return 하기

numbers의 길이는 1이상 100,00이하
numbers의 원소는 0이상 1,000이하

풀이

정렬로 풀어야 한다는 사실은 대부분 눈치챘을것이다.
차근차근 단계별로 각기 다른 정렬을 시도해보자.

1. 숫자 역정렬(내림차순)
단순히 숫자로 역정렬하면 다음과 같은 배열의 경우 문제가 된다.
[100, 99]
해당 배열을 정렬해서 합치면 10099이 된다. 하지만 99100이라는 수를 만들 수 있다. 따라서 배열에 있는 요소를 숫자로 인식하고 정렬하는 방식은 잘못되었다.

2. 문자열 정렬(내림차순)
문자열 정렬은 목차 정렬과 비슷하다고 생각한다.
예를들면, [42,413,4134,41,4]의 정렬은 4, 41, 413, 4134, 42가 됨을 확인할수있다.
목차 정렬과 비슷하다고 생각한 이유는 우리가 흔히 볼 수있는 책 목차에 있는 장의 정렬과 같기 때문이다.
4장
4-1장
4-1-3장
4-1-3-4장
4-2장
문자열 정렬에 대해 알아봤으니 해당 정렬을 이용해서 답을 구해보자.
예를 들어
[5, 87, 53] 을 역정렬하게 되면 [535, 5, 87] 이 나오게 된다. 이를 join하게 되면 '535587'이 나오는데 자세히 살펴보면 '553587'이 더 크게 나올 수 있다. 하지만 기본적인 정렬은 비슷한것 같으므로 해당 정렬 방법에서 조금만 변형하면 될것같다.

3. 문자열 정렬 응용
방금 위에서 보였던 예제는 치명적인 오류가 있다. 535이 5보다 더 높은 가치를 가지기 때문에 생겨나는 오류이다. 따라서 5를 세자리수로 변형하고 535와 비교해야한다. 단순히 5를 500으로 변형하게 된다면 여전히 5는 535보다 가치가 낮다. 어떻게 5를 변형시켜야지 제대로된 가치를 가질수있을에 대해 생각해보았다.

5는 555의 가치를 지닌다.
그 이유를 간단히 설명하면
5와 554를 앞뒤로 붙여가며 비교해보자.
5가 앞으로 갔을때 (5가 큰 경우)
5554
554가 앞으로 갔을때 (554가 큰 경우)
5545

554보다 5의 가치가 크다는것이 증명됬다.
다음으로는
5와 555를 앞뒤로 붙여가며 비교해보자.
5가 앞으로 갔을때 (5가 큰경우)
5555
555가 앞으로 갔을때 (555가 큰경우)
5555

둘의 경우가 같으므로 둘의 가치는 같다.
따라서 최소 자리수를(1자리) 최대 자리수(3자리)의 가치로 만들기 위해서 모든 자리수를 3번 연속한다. 그럼 모든 수가 3자리수의 이상의 가치를 가지게 되어 올바른 정렬이 가능하다.

코드

'''
Created by jun on 21/08/05
'''
def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x : x*3,reverse=True)
    return str(int(''.join(numbers)))

새로 알게된 사실

문자열 정렬 응용