[백준][Python] 18511번 큰 수 구성하기

18511번: 큰 수 구성하기

 

코드

from itertools import product
n, m = map(int,input().split())
k = list(map(int,input().split()))
k.sort(reverse=True)
length = len(str(n))

while 1:
	num = list(product(k, repeat=length))
	for a in num:
		a_num = int(''.join(map(str,a)))
		if a_num <= n:
			print(a_num)
			exit()
	length -= 1

 

설명

처음에는 숫자 한 자리씩 비교를 하는 식으로 코드를 짜봤는데 고려해야 될 경우의 수가 너무 많아서 다른 방법을 찾아봤다. product 함수를 사용하는 방법이었는데 주어진 집합 k 의 숫자들을 이용해서 중복순열을 구현할 수 있다.

만약 길이가 length인 모든 경우의 수 중에서 n보다 작은 수가 존재하지 않는다면 length를 1만큼 감소시켜서 위 과정을 반복한다.

 

---

<product 함수>

a=list(product([0,1,2],[0,1,2]))
print(a)

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

(2) repeat를 사용하는 경우

  - 동일한 리스트를 가지고 길이가 2인 모든 경우의 수

a=list(product([0,1,2],repeat=2))
print(a)

[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]