[백준🥈5] #18511 큰 수 구성하기 (python)

18511번: 큰 수 구성하기 (acmicpc.net)

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

예제 입력 1 

657 3
1 5 7

예제 출력 1 

577

 

✔️ Code

from itertools import product

n, k_num = map(int, input().split())
len_max = len(str(n))
k = list(input().split())

while True:
    tmp = list(product(k, repeat = len_max)) #repeat를 통해 몇 개를 뽑을지 결정
    result = []

    for i in tmp:
        if int("".join(i)) <= n:
            result.append(int("".join(i)))
    
    if len(result) >= 1:
        print(max(result))
        break
    
    else:
        len_max -= 1

 

✏️ Comment

• 이 문제는 product로 푸는 경우가 많은 것 같아서 나도 product 풀이를 참고했다. product는 중복 순열을 구하는 것이라고 한다. 예를 들어서 앞의 문제에서 썼던 combination의 경우 (a, b, c) 중 2개를 고를 때 (a, b) (a, c) (b, c) 로 경우의 수가 총 3개가 나오는데 product는 (a, a) (a, b) (a, c) (b, a) (b, b) (b, c) (c, a) (c, b) (c, c) 이렇게 9가지가 존재한다. 그 차이를 잘 알아두면 좋을 것 같다.
• 간과했던 점이 하나 있는데 풀이에서 (””.join) 을 사용해서 이를 int형으로 바꿔 n과 비교하는 부분이 있다. 이를 위해서 처음에 k의 수를 입력 받을 때 int 형이 아닌 str 형태로 입력 받아야 하는데 int로 입력 받아서 타입에러가 발생했었다.