(Python/🥈5)백준리즘알고리즘 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

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, k =map(int,sys.stdin.readline().split(" "))
lst = list(map(int,sys.stdin.readline().split(" ")))
res =[-1]
for lens in range(1,len(str(n))+1):
    for num in list(product(lst, repeat = lens)):
        if n >= int(''.join(map(str, num))):
            res.append(int(''.join(map(str, num))))
print(max(res))

 

중복순열을 사용해 길이가 1부터 n까지 중복순열을 담아 n보다 작으면 담아준다.

 

그 중에 최댓값 출력, 없으면 -1 출력된다.