[python] 백준 15649 - N과 M(1)

출처 : 백준, https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

 

쉬운 풀이

 

from itertools import permutations

if __name__ == '__main__':
  n, m = map(int, input().split())
  num_arr = [i for i in range(1, n + 1)]

  per_n = permutations(num_arr, m)

  for li in per_n:
    for num in li:
      print(num, end=" ")
    print()

 

쉬운 풀이는 바로 python의 itertools 라이브러리에서 순열 함수를 이용하는 것이다.

리스트와 뽑을 개수만 주면 순서대로 모든 순열 조합을 순서대로 정렬해서 되돌려준다.

물론 나는 이런 풀이를 하기 위해서 푼 건 아니었다.

 

어려운 풀이

 

visited = []
stack = []

def permutations(num_arr, total_count, depth = 0):
  if depth == total_count:
    for num in stack:
      print(num, end = ' ')
    print()
    return

  else:
    for index in range(len(visited)):
      if not visited[index]:
        stack.append(num_arr[index])
        visited[index] = True
        permutations(num_arr, total_count, depth + 1)
        stack.pop()
        visited[index] = False

if __name__ == '__main__':
  n, m = map(int, input().split())

  visited = [False] * n
  
  num_arr = [i for i in range(1, n + 1)]

  permutations(num_arr, m)

 

순열 알고리즘을 직접 구현해본 풀이이다.

해설은 이곳을 참고.

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

스터디원의 풀이

 

n,m = list(map(int,input().split()))
 
num = []
 
def check():
    if len(num) == m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in num:
            num.append(i)
            check()
            num.pop()
check()

 

난 바본가봐. 같이 코딩테스트 문제 풀이하는 스터디원이 하신 풀이인데

아.......visited 배열을 굳이 선언할 필요 없이 그냥 stack안에 in 연산자로 여부를 체크하면 되는거구나....를 깨달았다.

자바 원리를 보고 파이썬으로 바꾸면서 생각하지 못했던 부분인데,

방문 체크할 때는 파이썬에서 in 연산자로 하는게 코드도 훨씬 간결하고, 파이썬의 특성을 잘 살린 코드가 나오는 것 같다.

 

 

고찰

 

정말 visited를 사용하지 않고 구현할 수 있는 방법은 없을까하다가 결국 visited를 썼다.

하긴 그런 방법이 있었으면 python 순열 함수의 시간 복잡도가 그렇게 크진 않았겠지

원래 이 문제는 지금 고민중이었던 연산자 끼워넣기 문제를 풀려고 시도한 문제인데....하..