[Platinum V] 큰 수 만들기 - 16496

문제 링크

성능 요약

메모리: 34064 KB, 시간: 84 ms

분류

그리디 알고리즘, 정렬

제출 일자

2024년 2월 9일 21:25:13

문제 설명

음이 아닌 정수가 N개 들어있는 리스트가 주어졌을 때, 리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나머지 수는 0으로 시작하지 않으며, 0이 주어지는 경우 0 하나가 주어진다.

출력

리스트에 포함된 수를 나열하여 만들 수 있는 가장 큰 수를 출력한다. 수는 0으로 시작하면 안되며, 0이 정답인 경우 0 하나를 출력해야 한다.

풀이

아이디어

• 새로 배운것은 cmp_to_key를 통해 정렬의 key를 커스터마이징 할 수 있다는 것을 알았다.
• 이때 Tim Sort라는 방식으로 인덱스에 접근하고, 비교하는 두 인덱스가 compare의 각각 x와 y에 인자로 들어오게 된다.
• cmp_to_key는 리턴 값에 따라 정렬 순서를 정하는데, 1인경우(양수) 먼저 들어온 인자가 앞에 정렬되고, -1(음수)인경우 뒤에 정렬되도록 설계되어 있다.

코드

from functools import cmp_to_key

def compare(x,y):
    if str(y)+str(x)>=str(x)+str(y):
        return 1
    
    else:
        return -1

def solution(numbers):
    numbers=sorted(numbers, key=cmp_to_key(compare))
    return str(int("".join(map(str,numbers))))

input()
print(solution(list(map(int, input().split()))))

---

회고

• 프로그래머스에서 LV2로서, 쉬운듯 쉽지 않았던 문제였는데 그대로 백준에 플레티넘으로 있었다는 사실에 그나마 안도했다. 다만 문제 자체가 쉬운듯 쉽지 않았으며 새로 파이썬에서 정렬 방식에 대한 아이디어를 얻고 갔기 때문에 문제자체는 유익했다.