큰 수 구성하기 (백준 18511번)

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.

나의 풀이

import sys
from itertools import product
input=sys.stdin.readline
N,K=map(int,input().strip().split())
n_list=list(input().strip().split())
n_list.sort(reverse=True)

max_ans=0
end=False
for l in range(len(str(N)),0,-1):
    pn_list=list(product(n_list,repeat=l))
    for pn in pn_list:
        num=int(''.join(pn))
        if num<=N:
            print(num)
            end=True
            break
    if end:
        break

• itertools.product를 활용해서 모든 수의 조합을 구하고, 그 중 가장 큰 수를 출력하도록 코딩