백준 2164 - Python 리스트와 덱의 차이

이 문제를 딱 처음 봤을 때 리스트를 쓰면 무조건 풀릴 것 같았다.
사실 리스트말고 스택, 큐, 덱을 이론적으로만 알고 구현해본적도 없고,
파이썬에 함수로 내장되어 있다는 것도 이 문제를 풀면서 처음 알았다,,
더 찾아봐야겠다.

내 풀이(오답)

# 리스트 사용 -> 시간 복잡도 O(N) : 시간초과
# N = int(input())

# def shuffle_card(N):
#     card = []

#     for i in range(1, N+1):
#         card.append(i)
        
#     while len(card) > 1:
#         card.pop(0)
#         card.append(card[0])
#         card.pop(0)
        
#     print(card[0])    
    
# shuffle_card(N)

👉 리스트를 사용하여 풀고 Test case까지 다 맞춰서 맞을 줄 알았는데 시간초과가 떴다.
당황해서 while, for문을 없애서 시간복잡도를 낮추려고 해보았는데,
도저히 방법이 떠오르지 않아서 구글링으로 정답을 봤다.

정답

from collections import deque

N = int(input())

def shuffle_card(N):
    card = []
    for i in range(1, N+1):
        card.append(i)
    
    deque_card = deque(card)
    
    while len(deque_card) > 1:
        deque_card.popleft()
        deque_card.append(deque_card[0])
        deque_card.popleft()    
        
    print(deque_card[0])
    
shuffle_card(N)

👉 파이썬에 내장되어 있는 덱 함수를 통해서 리스트와 똑같은 구조로 구현했더니
시간초과가 뜨지 않고 정답으로 처리됐다.

리스트에서는 시간초과가 뜨고 덱에서는 뜨지 않는 이유를 알아보자!

리스트 VS 덱

1. 리스트

리스트에서는 하나의 요소를 삭제했을 때 내부적으로 그 뒤의 요소들을 한 칸씩 당기는 연산을 하게되어 시간 복잡도가 약 O(N)이다.

2. 덱

그에 반해 덱은 하나의 요소를 삭제해도 다른 요소를 제어할 필요가 없기 때문에
시간 복잡도가 O(1)이 된다.

덱의 주요 함수들

1. deque.append() : 리스트와 동일

2. deque.appendleft() : 맨 앞에 요소 추가

3. deque.insert() : 리스트와 동일

4. deque.pop() : 리스트와 동일

5. deque.popleft() : 맨 앞의 요소 삭제