[BOJ/Step14] 15651 : N과 M (3) (Python)

www.acmicpc.net/problem/15651

15651번: N과 M (3)

---

1 ~ N 중 중복 없이 M개의 수를 고르는 경우를 모두 출력하는 문제

 

(1) 리스트에 미리 m개만큼의 0을 저장한 후 index 순서대로 채워넣으며 출력하는 방법

  def sequence( seq, n, m, index ) :

    1. i가 1 ~ N까지 반복

    2. 리스트 seq[index]에 i 대입

    3. index+1 == m이면 seq를 출력

    4. 아니면 sequence( seq, n, m, index+1 ) 호출

# 15651-1.py

def sequence(seq, n, m, index):
    for i in range(1, n+1):
        seq[index] = i
        if index + 1 == m:
            print(' '.join(map(str, seq)))
        else:
            sequence(seq, n, m, index+1)


n, m = map(int, input().split())
nm = [0 for _ in range(m)]
sequence(nm, n, m, 0)

 

(2) 리스트에 하나씩 숫자를 추가하며 길이가 m이 되면 출력하는 방법

  def sequence( seq, n, m ) :

    1. 리스트 seq의 길이가 m인지 확인하여 m일때 seq 출력

    2. i가 1 ~ 1까지 반복

    3. 리스트 seq[index]에 i 추가

    4. sequence( seq, n, m ) 호출 => (1)과 다르게 seq의 길이로 판단하기 때문에 index를 전달하지 않아도 됨

    5. 리스트 seq 마지막 요소 삭제

# 15651-2.py

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


n, m = map(int, input().split())
nm = []
sequence(nm, n, m)

 

(3) itertools 모듈의 product함수를 이용하는 방법

# 15651-3.py

import itertools

n, m = map(int, input().split())
nm = [str(i) for i in range(1, n+1)]

a = list(itertools.product(nm, repeat=m))
for i in a:
    print(' '.join(i))

 

위부터 (3) (2) (1) 번 코드

(3)번이 제일 빠를거라고 생각하긴 했는데 이번에는 왜 (2)번이 (1)번보다 느린걸까

pop append가 시간이 좀 걸리나?