졍's 기술 블로그

N과 M (1)

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 512 MB
알고리즘 분류 : 백트래킹

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입출력

Algorithm

itertools 라이브러리 이용
1. itertools 라이브러리의 permutation() 이용해 1부터 N까지의 숫자 중 M개 선택해 모두 리스트에 저장
2. 리스트 오름차순 정렬 후 print

back tracking - 재귀 이용
1. stack에 들어있지 않은 숫자를 추가하고 재귀함수 호출
2. 재귀함수가 반환되면 pop
3. stack의 길이가 M이 되면 print

Code

# itertools library 이용
from itertools import permutations
N, M = map(int, input().split())

# 1부터 N까지의 숫자 중 M개를 선택하는 순열 리스트로 저장
nums = list(permutations(range(1, N+1), M))
# 리스트 오름차순 정렬
nums.sort()
# 출력
for i in nums:
    for j in i:
        print(j, end = ' ')
    print()

메모리: 34952 KB
시간: 236 ms

# back tracking - 재귀 이용

def back_tracking():
    
    # stack의 길이가 M이 되면 출력
    if len(stack) == M:
        print(' '. join(list(map(str, stack))))
    else:
        for num in range(1, N+1):
            # num이 stack에 없으면
            if num not in stack:
                # stack에 추가하고 재귀
                stack.append(num)
                back_tracking()
                # 재귀함수 반환되면 pop
                stack.pop()
                
N, M = map(int, input().split())
stack = []
back_tracking()

메모리: 30864 KB

시간: 208 ms