[BOJ/Step14] 15650 : N과 M (2) (Python)

www.acmicpc.net/problem/15650

15650번: N과 M (2)

---

1~N 중 중복 없이 M개의 수를 골라 오름차순으로 출력하는 문제

 

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

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

    1. i가 seq[index-1] ~ N까지 반복 => 이전 위치(왼쪽)의 수보다 큰 수만. 오름차순으로 출력해야하고 이미 나왔던 수열일 것이기 때문

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

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

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

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

# 15650-1.py

def sequence(seq, n, m, index):
    for i in range(seq[index-1] if seq[index-1] != 0 else 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) itertools 모듈의 combinations함수를 이용하는 방법

# 15650-2.py

import itertools

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

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

 

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

출력하는 수열 수가 줄어드니까 시간도 확 줄었다