[백준] 15650번: N과 M(2)_이게 왜 더 빨라...?

문제

문제만 봐서는 바로 와닿기 어려울 수 있지만,
예제를 보면 아!하는 문제.

전혀 어렵지 않다!
문제 읽기 시작한 후부터 거의 30분 만에 글쓰기까지 끝낼 것 같다.

풀이-조합을 이용

문제를 읽자마자 바로 생각난 것.
혹시나 시간 초과가 나나 싶었지만, 아니었다.

30840KB 84ms

from itertools import combinations

N, M = map(int, input().split())

numList = [i for i in range(1, N+1)]
# [1, 2, 3, 4]

for seq in combinations(numList, M):
    print(*seq)

혹시 입력받는 수의 제한이 8이 아니라 더 커진다면 어떻게 될 지 궁금하다.
다른 관련 문제가 있는지도 찾아봐야겠다.

풀이-백트래킹을 이용

분명히 백트래킹 알고리즘으로 찾은 문제인데,
백트래킹으로 안 풀 수 없지!

백트래킹은 간단히 말하자면,
조건에 맞는 해를 만들다가, 아니다싶으면 뒤로가기해서 다른 방법을 만드는 방법이다.
그래서 주로 재귀를 이용해서 많이 푸는 편이다.

30840KB 84ms

N, M = map(int, input().split())

numList = [i for i in range(0, N+1)]
# [0, 1, 2, 3, 4]

index = 0
# 이미 쓴 숫자인지 판별하기 위해 세팅
visited = [False]*(len(numList)+1)

def backTracking(result):

    # 개수에 맞게 꽉 찼다면 결과 출력
    if len(result) == M:
        print(*result)
        return
    
    # 쓴 것이 아니고, 담아놓은 결과가 비어있는 경우 담기
    # 쓴 것이 아니고, 담아놓은 결과가 담을 것보다 작으면 담기(오름차순)
    for i in range(1, N+1):
        if (visited[i]== False) and (len(result)==0 or i > result[-1]):
            visited[i] = True
            result.append(numList[i])
            # 재귀로 백트래킹 실행
            backTracking(result)
            # 재귀 끝난 뒤 빠져나와서 바로 직전에 담았던 것 제거하기
            visited[i] = False
            result.pop()

backTracking([])

이렇게 끝나면 시시하지...

30840KB 72ms

N, M = map(int, input().split())

numList = [i for i in range(0, N+1)]
# [0, 1, 2, 3, 4]

index = 0

def backTracking(result):

    # 개수에 맞게 꽉 찼다면 결과 출력
    if len(result) == M:
        print(*result)
        return

    for i in range(1, N+1):
        # visited를 쓰면 더 짧게 걸릴 줄 알았는데, 
        # 왜 not in을 쓰면 더 짧게 걸릴까...
        # 시간복잡도가 O(N)으로 알고 있는데 왜지...?
        if (i not in result) and (len(result)==0 or i > result[-1]):
            result.append(numList[i])
            # 재귀로 백트래킹 실행
            backTracking(result)
            # 재귀 끝난 뒤 빠져나와서 바로 직전에 담았던 것 제거하기
            result.pop()

backTracking([])

이 글을 적게 된 이유이자 의문 점인데,
사실 위의 경우에서 visited를 따로 만든 이유는 not in을 쓰지 않기 위해서였다.
둘의 시간 복잡도를 비교하면, O(1), O(N)이기 때문에
당연히 백트래킹의 첫번째 방법이 시간이 더 적게 나오겠지 했는데,
왜 때문에 not in을 쓰는 경우가 더 적게 나오는지 모르겠다.
설마 False, True 할당하는 데에서 시간이 더 많이 걸리나?
아니면 제한이 8 이하 뿐이라서 큰 차이가 나지 않는 것일까.

입력 받는 수의 제한이 좀 더 높아지면 어떻게 시간이 달라질 지 궁금하다.