문제 바로가기
문제:
숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다. 오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다. 오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오. 예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.
입력:
첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.
출력:
N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.
풀이:
import sys
n, m = map(int, sys.stdin.readline().split(" "))
lst = [str(input()) for _ in range(n)]
lst.sort(key=lambda x: x * 9, reverse=True)
# 딱 맞게 줌
if len(lst) == m:
print("".join(lst))
exit()
# 안 맞아서 숫자 더 뽑아야함, 가장길고 큰걸로 뽑음
lst.sort(key=len, reverse=True) # sort = nlogn // max,min = n
for i in range(m - len(lst)):
lst.append(lst[0])
lst.sort(key=lambda x: x * 9, reverse=True)
print("".join(lst))
정렬을 3번이나 해서 시간초과가 날 것 같았는데 max값이나 ,min을 찾는것보다 더 효율적이다.
데이터를 1,000,000,000 까지 받을수 있다.
만약 숫자가 1, 100, 10 일경우
다 최소 10자리 숫자로 맞춰주기위해서 1을 9개를 더 곱해준다
처음엔 그냥정렬을 때려버렸는데 이럴경우에는 맞는데 저럴경우에는 틀리고 반례가 많다.
정렬후 뽑는 갯수랑 주어진 숫자가 같으면 그냥 바로 출력하고
부족하면 부족한 만큼 가장 큰 숫자를 뽑아준다.
그러면 데이터가 다시 추가 됐기때문에 정렬 한 번 더 해주고 출력해 주면된다.
댓글