백준 - N 과 M(9)(15663)

문제 링크 ▶︎ 백준 N과M(9)15663

문제 전략

이 문제는 백트래킹 문제이다.
N과M 시리즈 중에는 시간 복잡도 문제로 까다로운 편이라고 생각한다.

중복된 배열을 검사하는 과정에서 before 이라는 변수를 선언하고, 이미 사용된 숫자인가를 검사한다.
어차피 lst 배열은 정렬된 배열이기때문에 중복된 배열인지를 검사하려면 직전 값만 비교하면 된다.

"이미 만들어진 배열인가"를 검사하면 시간 초과에 걸리고,
"직전에 쓴 숫자인가"를 검사하면 시간 초과에 걸리지 않는게 이 문제의 키포인트 인듯하다.

코드

import sys
input = sys.stdin.readline
n, m = map(int,input().split())
lst = list(map(int,input().split()))
lst.sort()

visit = [False] * n
def dfs(dep,l):
    if dep == m:
        print(*l)
        return
    before = 0
    for i in range(n):
        if not visit[i] and lst[i] != before:
            visit[i] = True
            before = lst[i]
            dfs(dep+1,l+[lst[i]])
            visit[i] = False
    

dfs(0,[])

개선 사항

① N 과 M 시리즈를 풀 때, 백트래킹 로직을 좀 더 생각해야할듯.
② 시간 복잡도 문제가 생길 때, 좀 더 깊게 고민하는 습관을 들여야할듯.