[ BOJ / 파이썬 ] 15649. N과 M(1)

음 .. ? 의외로 꽤 빨리 풀리고.. 이전 문제 풀이보다 실행시간도 줄었다..!

음 .. 실력이 늘긴 늘었나 진짜.

 

코드. 통과.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
visited = [0] * (n+1)
result = []
def recur(k):
  if k == m:
    print(*result)
    return

  for i in range(1, n+1):
    if not visited[i]:
      visited[i] = 1
      result.append(i)
      recur(k+1)
      visited[i] = 0
      result.pop()
recur(0)

 

처음에는

현재 방문한 배열(visited) 하나만 두고 k가 일정 깊이 도달했을 때 그냥 그 visited 싹 훑으며 체크된 애들을 출력할까 했었다.

n 범위가 1 ~ 8 밖에 안 되기 때문에 상관 없을 것 같기는 했는데 개인적으로 더 이해하기 쉽게 만드려고 result 배열을 따로 만들어서 현재 범위 안에 있는 애들은 append/pop 해줬다.

 

의외로 이 방법이 실행시간이 30%정도 줄었다.

 

 

이전에 풀었던 풀이

# 백트래킹 구현
n, m = map(int, input().split())
ans = []
def back():
    if len(ans) == m:
        print(" ".join(map(str,ans)))
        return
    for i in range(1, n + 1):
        if i not in ans:
            ans.append(i)
            back()
            ans.pop()
back()

아 그냥 visited를 안 써도 되는구나!! ㅋㅋㅋㅋ

아예 반대로 생각했었구나. visited 를 쓰는 풀이를 쓰고 값 저장은 안 해볼까? 하고 생각했는데

오히려 값은 저장하고 in을 통해서 검사를 해주고 visited는 안 써도 되는거였다.

 

 

추가적으로

 

해당 문제에 수학적인 개념을 적용하고, 파이썬 라이브러리를 사용한 버전도 같이 복습하기.

 

1부터 n까지 자연수 중에서 m개를 ' 중복없이 ' 고르는 ' 수열 '

 = permutations

itertools 라이브러리의 permutations 메서드를 사용하면 된다.

 

from itertools import permutations
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
result = permutations(range(1,n+1), m)
for res in result:
  for i in res:
    print(i, end=" ")
  print("")

permutations( 범위, 고를 개수 )

 

사전순으로 출력하는 것이 문제의 조건인데, 여기서 range의 인덱스를 키워가기에 자동으로 해당 조건 완성된다.

위에서 permutations를 사용하지 않는 경우에도 for문으로 증가했기에 역시 해결됐음 : )