[백준/16496] 큰 수 만들기 (Python)

Problem : https://www.acmicpc.net/problem/2666

2666번: 벽장문의 이동

 

Difficulty : Platinum 5

 

Status : Solved

 

Time : 00:11:46

 

---

 

문제 설명

 

 

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

5
3 30 34 5 9

 

출력 예시

 

9534330

 

 

---

 

풀이

 

고려해 주어야 할 게 많아 보이지만, N <= 1000이므로 O(N^2)의 모든 시간 내에 정렬하면 된다. 파이썬의 내장 cmp 함수를 이용하면 더 빠르다.

 

문제는 정렬 기준. 어떻게 정렬해야 할까. 단순히 a, b 두 수로 가장 큰 수를 나열하여 만든다고 가정하면, a+b와 b+a중 더 큰 수가 오도록 둘을 정렬하면 된다. 이는 전체 문제로도 그리디하게 확장할 수 있다. 즉 정렬 기준을 위와 같이 두고, 버블 소트 등을 사용하면 바로 풀리게 된다.

 

 

풀이 코드

from functools import cmp_to_key

def cmp(a, b) :
  if a+b > b+a :
    return -1
  elif a+b == b+a :
    return 0
  else :
    return 1

N = int(input())
num_list = sorted(input().split(), key = cmp_to_key(cmp))
print(int("".join(num_list)))

풀이 완료!