[백준1442번] 숫자의 신 / Python3

문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

예제 입력 1

3 3
3
2
7

예제 출력 1

732

나의 풀이

이 문제의 핵심은 숫자들을 정렬할때 문자열로 두 숫자를 합치고 큰 것을 우선으로 정렬해주는 것이었다.

따라서 문제의 해결법은 다음과 같다.

1. 주어지는 k개의 숫자 중 가장 큰 숫자를 찾는다.
2. (n-k)개만큼 가장 큰 숫자를 nums 리스트에 추가한다.
3. 만들어진 리스트를 정렬한다.
   • 이때 두 개의 숫자를 순서를 바꾸어 문자열로 합쳐보고 큰 것을 앞으로 정렬한다.
   • int(str(a) + str(b))와int(str(b) + str(a))를 비교.
   • cmp_to_key에 해당 로직을 만들어 설정한다.

코드

# 1422번 숫자의 신
import heapq
from functools import cmp_to_key

def compare(a, b):
    return int(str(a)+str(b)) - int(str(b)+str(a))

k, n = map(int, input().split())
nums = [int(input()) for _ in range(k)]

max_num = max(nums)
for _ in range(n - len(nums)):
    nums.append(max_num)
nums= sorted(nums, key=cmp_to_key(lambda a, b: -1 if int(str(a)+str(b)) > int(str(b)+str(a)) else 1))
print(*nums, sep='')