문제 설명
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" |
내 풀이
먼저 말하자면 아래 코드는 효율이 좋지 않다.
다른 사람들의 코드를 보며 나도 좀 더 간결한 코딩을 하고 싶다는 생각을 하며 풀어봤다.
효율이 개선된 코드는 후술하겠다.
def solution(numbers): return str(int("".join(sorted(list(map(str, numbers)),key=lambda x: 3*x, reverse=True))))
정확성 테스트: ~1270.33ms / 28.1MB
numbers를 스트링 형태로 리스트에 담고 적절한 순서로 배열할 것이다.
그 순서라는 것은 어떻게 될까?
예를 들어 ["4", "5", "51", "54", "55", "551", "556", "59", "6"]이라는 배열이 어떻게 정렬 돼야 하는지 생각해보자.
배치할 때 제일 큰 수를 만들어야 하므로 정렬한 리스트의 첫 번째 값은 6이다.
그리고 59, 556이 온다.
그 뒤로는 5가 먼저오나 55가 먼저 오나 상관없다. 즉 동등한 우선도를 갖는다.
그 뒤 551, 54, 51, 4 순서로 배열이 된다.
정렬된 리스트는 ["6", "59", "556", "55", "5", "54", "51", "4"]이다.
자세히 살펴보면 규칙을 알 수 있다.
각 요소들을 반복했을 때 스트링으로서 큰 값을 먼저 배열하는 것이다.
666666...
595959...
556556...
555555...
555555...
545454...
515151...
444444...
이렇게 보면 좀 더 알기 쉬울 것이다.
따라서 sorted의 key에는 lambda x: 3*x 라는 함수 사용한다.
스트링 형태로 바꾼 numbers의 원소를 세 번씩 반복해서 대소를 내림차순(reverse=True)로 비교하는 것이다.
numbers 원소는 1000이하이므로 세 번씩만 반복해도 대소 비교에 지장이 없지만, 불안하다면 4번 반복해줘도 전혀 문제가 없다.
이렇게 정렬한 sorted(~) 리스트를 join을 이용해 연결해준다.
굳이 int로 바꿨다가 str으로 다시 변환하는 이유는 혹여 0이 맨 앞으로 오면 제대로된 반환값이 아니게 되기 때문이다.
애초에 numbers는 int 형태로 담겨있기 때문에 return값 맨 앞에 0이 붙어서 출력되는 것은 numbers에 0이 포함된 경우를 제외하면 없다.
게다가 numbers의 나머지 요솟값이 자연수라면 스트링 형태로 정렬했을 때 0이 다른 자연수보다 앞에 오는 경우는 없기 때문에 필연적으로 모든 numbers에 0이 두 개 이상 담긴 경우에만 "00", "0000"과 같은 이상한 값이 반환된다.
따라서 int()를 굳이 모든 경우에 씌워서 코드를 비효율적으로 만들 필요는 없다.
그렇게 개선된 코드가 아래와 같다.
def solution(numbers): if numbers == [0]*len(numbers): return "0" else: return "".join(sorted(list(map(str, numbers)),key=lambda x: 3*x, reverse=True))
정확성 테스트: ~56.62ms / 27.7MB
