from itertools import *
def solve():
if len({*N})==K:
return N
for i in range(1,len(N)+1):
result = []
inuse = {*(N0:=N[:-i])}; notuse = {*map(str,range(10))}-inuse; k = K-len(inuse)
if 0<=k<=i:
for C in combinations(notuse,k):
C = {*C}
for H in combinations_with_replacement(inuse|C,i-k):
willuse = [*H,*C]
for n in range(int(N[-i])+1,10):
n = str(n)
if n in willuse:
willuse.remove(n)
result.append(N0+n+"".join(sorted(willuse)))
if result:
return min(result)
return "1"+"0"*(max(len(N)+1,K)-K+1)+"".join(map(str,range(2,K)))
N,K = input().split(); K = int(K)
print(solve())
조합과 중복조합으로 해결하였다.
디지털 카운터 [백준 1020번] 디지털 카운터 (Python3) (tistory.com) 문제와 유사한 방식으로 해결하였다.
풀이를 설명하면,
1. 숫자를 1~L(L=len(N))=i 자리수까지 자른다.
2. 잘라내고 남은 숫자들을 구성하는 숫자들을 inuse로 저장하고, notuse에 0~9 중에서 inuse에 포함하지 않은 숫자들을 저장한다.
3. notuse에서 K-(inuse 개수)=k개의 숫자를 combinations으로 뽑고 com으로 저장한다.
4. i-k개의 숫자를 inuse와 com을 합친 집합에서 중복조합으로 뽑는다.
5. 3에서 뽑은 숫자와 4에서 뽑은 숫자를 중 원래 숫자보다 크면서 가장 작게끔 정렬하고 result에 넣는다.
6. result에서 가장 작은 값을 출력하고, result에 숫자가 없으면 자릿수를 늘려가며 반복한다.
7. 자리수를 L까지 했는데도 찾지 못했다면 "1"+"0*(max(L+1,K)-K+1)"+"2~K까지 숫자"를 출력한다. (예를들어 L=3, K=5라면 10234 출력)
중복조합을 이용해서 간단하게 해결하였다. 이 문제도 디지털 카운터 문제처럼 조합을 이용하는것이 아닌 DP를 이용해서 푸는 문제라고 한다. DP를 이용한 풀이도 한번 고민해보아야겠다.
오늘의 교훈) itertools는 유용하다.