[백준15649&파이썬] 파이썬에서 순열을 구해야 할때

# 문제

백준 15649 N과M (1) 파이썬 풀이

15649번: N과 M (1)

# 코드

import sys
from itertools import permutations

N,M = map(int,sys.stdin.readline().split())
targets = [i for i in range(1,N+1)]
# # print(targets)
# 
# 중복없이 M개를 고른 수열
#   조합을 사용한다.
for permu in permutations(targets,M) :
  print(*permu)



# 순열 -> 백트래킹을 활용하는 방법
visit = [False] * (N+1)
def dfs(node ,length) :
  global visit
  global M

  if M <= length :
    print(node)
    return

  for target in targets :
    if visit[target] == False :
      visit[target] = True
      next = node + " " + str(target)
      dfs(next,length+1)
      visit[target] = False

for i in range(1,N+1) :
  visit[i] = True
  dfs(str(i),1)
  visit[i] = False

# 풀이

• 중복없이 순열을 구하는 문제이다.
• nPm의 순열을 푸는 것과 같다.
• 파이썬의 itertools의 permutations모듈을 사용하여 해결 할 수 있다.
• 백트래킹을 이용해서 문제를 해결 할 수 있다.
• 모듈을 사용하는것보다, 직접 구현한 코드의 실행속도가 더 빨랐다.
• O(n!)로 상당히 느린 시간복잡도를 가진다.