[백준15651&파이썬] 중복순열을 구하는 두가지 방법

# 문제

백준 15651 N과M 3 파이썬 풀이

15651번: N과 M (3)

# 코드

import sys
from itertools import  product

N,M = map(int,sys.stdin.readline().split())

targets = [i for i in range(1,N+1)]

# 중복순열의 문제
def dfs(mstr,cnt) :
  global M
  if cnt == M+1 :
    print(mstr)
    return

  for target in targets :
    next = mstr + str(target) + " "
    dfs(next,cnt+1)
dfs("",1)


# itertools의 product 활용
for pro in product(targets,repeat = M) :
  print(*pro)

# 풀이

• 중복순열을 만들어야 하는 문제이다.
• 방문 + 백트래킹을 사용해서 순열의 문제를 풀었다면, 방문을 표기하지 않으면 중복순열의 해당하는 값을 뽑을 수 있다.
• product모듈을 사용해서 쉽게 구할 수 있다. product( 배열, repeat = 뽑을 개수)
• 속도는 직접구현시 632ms, product사용시 1932ms로 직접구현시가 훨씬 빠른 시간을 가짐을 알 수 있다.