[코딩테스트] 백준 N과 M (1) 파이썬(Python)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

n, m = map(int, input().split())

result = []

def solve():
  if len(result) == m:
    print(' '.join(map(str, result)))
    return
  for i in range(1, n+1):
    if i not in result:
      result.append(i)
      solve()
      result.pop()

solve()

저는 두가지 방법을 이용하여 문제를 해결하였습니다.

 

첫번째 방법으로는 재귀를 이용한 방법입니다.

재귀의 종료조건으로는 결과를 담을 result의 크기가 주어진 m과 동일하다면 결과를 반환하고 함수를 종료합니다.

1부터 주어진 n까지의 숫자를 반복하는데 i가 result에 없다면 result에 추가하고 다시 재귀함수를 호출합니다.

 

저는 아래의 사이트를 이용하여 디버깅을 진행하였습니다.

Python Tutor: Learn Python, JavaScript, C, C++, and Java programming by visualizing code

 

예를들어 n = 3, m = 2 가 주어진다면

위의 그림처럼 먼저 result = [1] 됩니다.

다음 재귀함수 solve()가 호출이 됩니다.

result에는 이미 1이 존재하기 때문에 넘어가고 2를 result에 넣게됩니다.

result = [1, 2]

다시 재귀함수를 호출합니다.

이때 result의 크기가 m과 동일하기 때문에 print 문을 출력하고 함수를 종료합니다.

이렇게 이전에 실행했던 반복문으로 돌아와서  result = [1, 2] 에서 result.pop() 실행이됩니다.

result = [1]이 됩니다.

반복문의 i가 3이 되어 result = [1,3]이 됩니다.

역시 재귀함수가 호출이 되고 종료조건에 의하여 출력이되고 함수를 종료합니다.

result.pop()이 실행이되어 result = [1]이 됩니다.

이때 반복문이 종료가되어 재귀함수가 종료가 됩니다 

첫번째로 실행되었던 solve()의 반복문으로 돌아옵니다.

result = [1]에서 result.pop()이 실행이 되어 result = []가 됩니다.

다음은 i가 하나가 증가 i=2가 되어 함수를 진행합니다.

나머지 과정은 생략하도록 하겠습니다.

 

첫번째 방법은 위와 같은 과정으로 해결하였고 두번째 방법은 아래의 코드로 해결하였습니다.

from itertools import permutations
n, m = map(int, input().split())
array = [i for i in range(1, n+1)]
result = []

for lst in permutations(array, m):
  print(' '.join(map(str, lst)))

itertools의 permutations 라이브러리를 이용하여 해결하였습니다.

print(list(permutations(array, m)))

 

n=3, m=2 일때 위의 함수를 실행하면 아래와 같이 순열의 결과가 나오게 됩니다.

반복문을 통하여 결과를 알맞게 출력을 하여 문제를 해결하였습니다.

 

 

백준에서 permutations를 사용했을 때의 결과가 그렇지 않았던 첫번째 방법보다 더 빠르게 나온것을 확인할 수 있었습니다.