[백준/1422] 숫자의 신 (Python)

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

1422번: 숫자의 신

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:10:31

 

---

 

문제 설명

 

 

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

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

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

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

3 3
3
2
7

 

출력 예시

 

732

 

 

---

 

풀이

 

그리디 + 정렬 문제는 파이썬이 정말 풀기 쉬운 조합이라고 개인적으로 생각한다.

 

첫 번째로, 우리는 각 수를 최소 1개씩을 써야 하므로, 이 수들을 정렬할 방식을 생각해야 한다. 두 수가 x, y일때, 두 수를 이어붙인 수를 (x, y)라고 두자. 그렇다면 (x, y) > (y, x) 일 때 x, y 순으로 정렬되어야 한다. 이런 식으로 모든 수에 대해 정렬 기준을 잡고 정렬을 수행하면 된다.

 

두 번째로, 우리는 그리디하게 K개의 수 중 중복해서 사용했을 때 가장 높은 수가 되는 경우를 사용해 봄직하다. 이 경우는 단순히 가장 큰 수를 사용하면 된다. 즉 여기서 선정된 수는 N-K+1개, 나머지 수는 1개씩 사용하여 앞선 정렬 결과대로 이어붙이면 정답을 얻을 수 있다.

 

 

풀이 코드

from functools import cmp_to_key
import sys
input = sys.stdin.readline

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

K, N = map(int, input().split())
M = N-K
nums = [int(input()) for _ in range(K)]
nums.sort(key = cmp_to_key(largest_sort))
best_val = max(nums)

ans = ''
for n in nums :
  if n == best_val :
    ans += str(n)*(M+1)
    best_val = ''
  else :
    ans += str(n)
print(ans)

풀이 완료!