[BOJ/Step14] 15649 : N과 M (1) (Python)

www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

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

 

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

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

    1. i가 1 ~ N까지 반복

    2. 리스트 seq[:index]에 대입하려는 i 가 있는지 확인하여 있으면 continue => 중복 없이 m개의 수를 고르기 때문

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

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

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

# 15649-1.py

def sequence(seq, n, m, index):
    for i in range(1, n+1):
        if i in seq[:index]:
            continue
        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에 대입하려는 i 가 있는지 확인하여 있으면 continue => 중복 없이 m개의 수를 고르기 때문

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

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

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

# 15649-2.py

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


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

 

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

# 15649-3.py

import itertools

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

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

 

위부터 순서대로 (3) (2) (1) 번 코드

확실히 모듈 함수를 이용하는게 빠르다..