[Python] 백준 #18511- 큰 수 구성하기[try_again]

문제

---

18511번: 큰 수 구성하기

코드

---

My answer

import sys
from itertools import permutations
input=sys.stdin.readline

n,k=map(int,input().split())
num=list(input().split())*len(str(n))
k=len(str(n))
result=[]

for i in range(1,k+1):
    for j in permutations(num,i):
        tmp=int(''.join(j))
        if(tmp<=n):
            result.append(tmp)
print(max(result))

Another answer

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))  # repeat을 통해 몇개를 뽑을지 설정한다.
    ex = []
    for i in temp:
        now=int(''.join(i))
        if now <= n:
            ex.append(now)
    if len(ex) >= 1:
        print(max(ex))
        break
    else:
        length -= 1

풀이

---

우선 맨처음에 문제가 안풀렸던 이유는 문제를 잘 이해하지 못해서였다. 주의할 점은 예를들어 n이 4111이고 k의원소개수가 3 즉 입력값이 4111 3 그리고 k가 2 3 3 일떼, 정답은 3333이 나와야한다. 나는 중복되는건 알고있었는데, 만들어야 하는 수가 k의 원소개수 즉 위에서는 3인줄알고 세자릿수를 구했었다. 그게아니라 n과 동일한 자릿수까지 중의 수 중에서 찾아야 한다. 내 코드는 메모리 초과가 났는데 나는 product라는 함수를 몰라서 중복순열을 뽑기위해서 k의 원소들을 n자릿수만큼 곱해서 넣어줬다. 그런데 이럴경우 n이 무수히 커지면 메모리초과가 난다. 그래서 찾아보니 product라는 중복순열 함수가 있었다.. permutations와 combination는 알고있었는데 ㅠㅠ product는 앞의 두개와는 달리 인자값에 repeat=n으로 몇개를 뽑을지 정해줘야한다. peromutations와 combinations는 그냥 리스트와,n을 넣어주면된다. 그래서 위의 코드는 우선 n과 동일한 자리부터 시작해서 점점 자릿수가 낮아지면서 풀게된다.