BruteForce08큰 수 구성하기(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의 원소로만 구성된 가장 큰 수를 출력한다.

풀이

• 최대 8자리수에 3가지 요소가 들어갈 수 있다.
• 순열이지만 중복이 허용된다.
• 따라서 itertools-product를 사용했다.
• 주의할점 : 만약 N = 1938이고 배열은 {8,9,7}이라고 하면 출력해야 될 수는 999로 자릿수가 다르다. 이부분을 주의해서 코드를 작성해야한다. 아래 코드에서는 length를 1씩 깎아주면서 반복하도록 작성

했다.

코드

import sys
sys.stdin = open("input.txt", "rt")
input = sys.stdin.readline
from itertools import product
N,K = map(int,input().split())
arr = list(map(str,input().split()))
length = len(str(N))

while(True):
    # 순열이지만 중복이 허락되도록 한다
    temp = list(product( arr, repeat=length))
    # product는 중복순열(순서o,중복o), permutations는 순열(순서o,중복x), combination은 조합
    answer = []

    for i in temp :
        if int("".join(i)) <= N :
            answer.append(int("".join(i)))
    print(answer)

    if len(answer)>= 1:
        print(max(answer))
        break
    else : # 순열이 모두 N보다 클 경우 자리수를 줄인다.
        length -=1