문제 설명
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" |
접근
- 맨 앞 자리를 가지고 기수 정렬을 하면 되지 않을까?
우선 맨 앞자리가 크면 클 수록 문자열로 이어붙였을 때 큰 수가 되는 것이 자연스럽다고 생각했다. 그래서 맨 앞 자리를 기준으로 기수 정렬을 한다면 9나 91 같은 수들을 하나의 큐 안에 모을 수 있기 때문에 내림차순으로 기수 정렬을 한다면 되지 않을까하고 생각했다.
봉착한 문제
-
3과 30
입출력 예제에서 두 번째 테스트 케이스를 보면 3과 30 중 3이 우선순위를 가지는 것을 알 수 있다. 이처럼 뒤에 0이 붙어있다면 다른 수들에 비해 우선순위가 떨어짐을 알 수 있다. 이를 고려해 정렬 우선순위를 단순한 내림차순으로 하는 것으로는 안 될 것이라 생각했다. -
[100, 10]
위 문제를 해결하고 나서 보니 문제는 100과 10인 경우에는 10이 우선순위가 더 높다는 것이다. 왜냐하면 10은 두 자리 수고, 100은 세 자리 자연수이기 때문이다. 그래서 길이도 고려해야 하는 것인가라는 의문이 생겼다. (이때쯤부터 슬슬 문제를 잘못 접근하고 있는 것이 아닌가라는 생각이 들기 시작했다.) -
[0, 0, 0, 0, 0]이 00000으로 나옴
이 문제는 단순한 조건문으로 해결할 수도 있고, 문자열을 join할 때 처리할 수 있는 등, 쉽게 처리할 수 있는 문제이므로 이는 금방 해결했다. -
[10, 101]
기껏 정렬을 해 놨더니 이번에는 10과 101이 문제다. 이번 경우에서는 101이 우선순위가 더 높다. 하지만, 2번째 문제에서 얘기했든 문자열 길이로 비교하면 해당 문제는 10101로 문자열이 만들어진다. 여기서 이 문제를 풀 길이 도저히 보이지 않아 결국 다른 사람의 풀이를 봤다.
다른 사람의 풀이
def solution(num):
num = list(map(str, num))
num.sort(key = lambda x : x*3, reverse = True)
return str(int(''.join(num)))처음에는 이렇게 간단한 코드로 짤 수 있다는 것에 놀랐지만 코드를 해석하면서 이 사람의 문제해결력에 감탄을 하지 않을 수 없었다.
정렬할 때 기존 문자열을 그대로 사용하는 것이 아닌 3번 연속된 문자열로 변형해 정렬에 사용한 것이다(예를 들어, [3, 30]이라면 [333, 303030]으로 정렬에 사용한 것).
문자열을 연속적으로 붙여서 사용하면 정렬할 때 위의 경우는 모든 수를 최소 3자리로 맞추어 비교하게 된다. 어차피 배열의 요소도 1000이하고, 1000의 경우 0 다음으로 우선순위가 낮기 때문에 모든 수를 최소 3자리로 맞추어 정렬하는 것이 가장 효율적이다.
3자리가 아닌 2자리로 맞춘다면 여전히 숫자의 우선순위가 잘못된다. 가령 9와 991을 정렬한다고 하면, "99", "991991"이 되므로, 여전히 991이 우선순위를 가지기 때문이다.
