졍's 기술 블로그

N과 M (2)

티어 : 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. 리스트 오름차순 정렬
3. 각 원소들이 오름차순으로 정렬되어있는 순열만 answer에 저장해 출력

백트래킹 - 재귀
1. stack이 비어있는지 확인
1.1. stack 비어있으면 stack에 num 추가하고 재귀함수 호출 후 재귀함수 return되면 pop
1.2. stack 비어있지 않으면 stack에 없는 값 중 stack의 마지막 숫자보다 큰 수 append하고 재귀함수 호출 후 재귀함수 return되면 pop
2. stack의 길이가 M과 같으면 stack print

Code

# itertools library

from itertools import permutations
N, M = map(int, input().split())
answer = []
temp = list(permutations(range(1, N+1), M))
temp.sort()
for i in temp:
    flag = False
    for j in range(1, M):
        if i[j-1] > i[j]:
            flag = True
    if not flag:
        answer.append(i)
        
for i in answer:
    for j in range(M):
        print(i[j], end = ' ')
    print()

메모리: 34952 KB
시간: 136 ms

def back_tracking():
    
    # stack의 길이가 M이면 print
    if len(stack) == M:
        print(' '.join(list(map(str, stack))))
    else:
        for num in range(1, N+1):
            # stack이 비어있으면
            if not stack:
                # stack에 num 추가
                stack.append(num)
                # 재귀함수 호출
                back_tracking()
                # 재귀함수 return되면 pop
                stack.pop()
            # 스택이 비어있지 않으면
            # num이 stack에 없고 num이 stack의 마지막 숫자보다 크면
            elif num not in stack and num > stack[-1]:
                # stack에 num 추가
                stack.append(num)
                # 재귀함수 호출
                back_tracking()
                # 재귀함수 return되면 pop
                stack.pop()
                
N, M = map(int, input().split())
stack = []
back_tracking()

메모리: 30864 KB
시간: 76 ms