문제 설명
📃 문제 링크
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] | 9534330 |
문제 풀이
어려웠다!!
numbers의 요소를 모두 문자열로 바꿔 내림차순으로 정렬한다는 것 까지는 생각했다. 하지만 그냥 정렬하면 numbers가 [3, 30, 34, 5, 9]일 때 ['9', '5', '34', '30', '3'] 이렇게 정렬이 된다. 가장 큰 수가 되려면 ['9', '5', '34', '3', '30']의 순서로 정렬되어야 하는데, 이 방법을 찾지 못했었다.
그래서 다른 사람의 풀이를 참고해서 풀었다.
문제의 제한 사항에서 numbers의 원소는 0 이상 1000 이하라고 했기 때문에, 모든 원소가 세 자리 이상이 될 수 있도록 문자열인 각 원소에 3을 곱해서 정렬해준다.
3을 곱해주면 34, 3, 30은 343434, 333, 303030이 되고, 문자열이기 때문에 맨 앞자리부터 아스키 코드로 비교해서 원하는 순서로 정렬이 된다.
예외적으로, [0, 0, 0, 0, 0]일 경우 정렬한 리스트를 그대로 리턴하면 00000이 되기 때문에 int형으로 변환한 후 다시 str로 변환해서 리턴해준다.
알게 된 것
numbers2 = [str(x) for x in numbers]위의 코드보다
numbers2 = list(map(str, numbers))이 코드가 아주 조금 더 빠르다!
리스트를 sort 또는 sorted 함수로 정렬할 때, 정렬하는 기준을 key 값으로 줄 수 있다. 함수를 key값으로 주면 되는데, 간단해서 lambda를 쓸 수 있는 경우는 lambda를 쓰고 그렇지 못한 경우에는 아래처럼 함수를 구현한 뒤 functools.cmp_to_key로 연결해주면 된다.
from functools import cmp_to_key
def func(x, y):
if x[1] != y[1]:
return x[1] - y[1]
else:
return y[0] - x[0]
arr.sort(key=cmp_to_key(func))소스 코드
.png)
