[ Python ] 15654번 : N과 M (5)

코딩테스트 해설

백준 15654번: N과 M (5) 

문제 유형 : 백트래킹

작성 코드

import sys

N, M = map(int, sys.stdin.readline().split(" "))
sequence = sorted(map(int, sys.stdin.readline().split(" ")))

def recurion_tree(current_select: list, depth: int) -> list:
    if depth == M:
        return [current_select]
    results = []
    for num in range(N):
        if num not in current_select:
            results.extend(recurion_tree(current_select + [num], depth + 1))
    return results

for data in recurion_tree([], 0):
    print(" ".join(map(str, [sequence[num_idx] for num_idx in data])))

접근 방식

1. 이 코드는 재귀 함수(recurion_tree)를 이용하여 N개의 수 중 M개를 선택하는 모든 순열을 생성합니다. 
   주어진 수열은 먼저 정렬되어 있으며, 이는 출력되는 순열이 사전 순으로 정렬되어야 함을 보장할 수 있습니다.
2. 재귀 함수는 현재까지 선택된 수의 인덱스 리스트(current_select)와 현재의 깊이(depth)를 매개변수로 받습니다. 
   깊이가 M에 도달하면 현재 선택된 리스트를 결과에 추가합니다.
   
3. 각 단계에서 N개의 모든 수를 반복하면서, 이미 선택된 수의 인덱스를 제외하고 선택된 인덱스 리스트에 추가한 후 다음 깊이로 재귀 호출을 진행합니다.

개선 사항

1. 현재는 실제 값이 아닌 index를 저장하고 있습니다. 따라서 해당 부분을 실제 표기하는 값으로 한다면, 출력 시 별도로 indexing을 하는 부분을 줄일 수 있습니다
2. backtracking 문제지만 단순히, 나열을 한 뒤 depth를 체크한 뒤, 각 영역을 출력할 수 있는 형태로 변환 하였습니다.
   만약 주어진 입력이 조금만 더 컸다면 시간초과가 발생했을 것 같습니다.

---