💡코딩테스트/백준

[백준 1422 | python] 숫자의 신

두_두 2023. 6. 16. 18:29
 

1422번: 숫자의 신

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다

www.acmicpc.net

숫자의 신

문제

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

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

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

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

 

 

풀이

functools의 cmp_to_key 이용하여 조건에 따라 정렬되게 한다.

 

functools.cmp_to_key

cmp_to_key안에 지정한 함수의 리턴 값에 따라 순서가 지정된다
  • -1 : 먼저 들어온 값이 나중에 들어온 값보다 앞에 정렬
  • 0 : 기존의 순서 그대로
  • 1 : 나중에 들어온 값이 먼저 들어온 값보다 앞에 정렬

 

from functools import cmp_to_key

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

max_num = max(num)
for _ in range(n - len(num)):
    num.append(max_num)


def compare(a, b):
    x = int(str(a) + str(b))
    y = int(str(b) + str(a))

    if x >= y:
        return -1  # -1이면 순서 바꾸기
    else:
        return 1  # 1이면 그대로


num = sorted(num, key=cmp_to_key(compare))

print(*num, sep='')

 

728x90