[코딩테스트 연습] 정렬(Sort) - 가장 큰 수
문제 설명
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
- numbers의 길이는 1 이상 100,000 이하입니다.
- numbers의 원소는 0 이상 1,000 이하입니다.
- 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
입출력 예
| numbers | return |
|---|---|
| [6, 10, 2] | "6210" |
| [3, 30, 34, 5, 9] |
문제 해결 방법
- 빈 문자열로 수를 초기화 한다.
- 가장 크게 만들 수 있는 수를 고른다(정렬한다).
- 그 수를 현재 수에 이어 붙인다.
- 모든 수를 다 사용 할때 까지 반복한다.
"크게 만드는 수"의 기준
예제 1
3, 32, 33, 34가 주어졌다고 가정해보자.
3 vs 32
332(3을 앞에 32를 뒤에) vs 323(32를 앞에 3을 뒤에) 랑 같은 말이다. 332 가 더 크게 만들 수 있는 숫자이기 때문에 3 을 고른다.
3 vs. 33
위 방법과 같이 333 vs 333 과 같아. 즉, 동일한 우선 순위 이다.
3 vs. 34
334 vs. 343이다. 이 경우 343가 더 크므로 34를 선택한다.
예제 2
34, 342, 343, 344가 주어졌다고 가정해보자.
34 vs. 343
위 경우를 살펴 보자. 34343(34 왼쪽, 343 오른쪽) vs. 34334(343 왼쪽, 34 오른쪽) 이 때는 34343이 더 크므로 34를 골라야한다.
정리
즉, 정렬을 할 때 이러한 기준으로 비교를 해서 정렬을 해야한다.
34 vs 343
34의 경우, 수를 가장 크게 만드는 것을 우선으로 정렬이 되었있다고 가정하면, 34보다 뒤에 올 수있는것은 커 봐야 34를 넘지 못한다. 그걸을 쭉 이어 붙히면 3434343434...이런 반복이 된다.
343의 경우 이것을 쭉 이어 붙히면 343343343343이런꼴이 된다. 문제의 제안 조건이 1000이하 이기 때문에 길어 봐야 4글자이다. 4글자를 끈어서 비교하면된다.
코드 구현
def solution(numbers):
numbers = list(map(str, numbers))
numbers = list(sorted(numbers, key=lambda x: (x*4)[:4], reverse=True ))
return str(int("".join(numbers)))