백준(BAEKJOON) 2164 카드2 - 파이썬(python)

 

 

리스트의 첫 원소를 지우고 그 다음 원소를 맨 뒤로 보내는 간단한 문제였다.

 

처음에는 list의 pop과 append를 사용했었는데 시간초과가 떠서 다시 찾아보니

deque를 사용해서 풀어야 하는 문제였다.

 

처음 풀었던 것처럼 list.pop(0)을 하게되면 뒤에 남은 원소들을 모두 앞으로 땡겨오기 때문에 시간복잡도가 O(N)이 되는 반면에

deque의 leftpop을 사용하면 제거하고 뒤 원소들의 메모리를 건드리지 않기 때문에 시간복잡도가 O(1)이 되어 속도면에서 압도적이다.

 

N의 크기가 커질수록 deque의 성능이 우수해지며, 특히 left관련 함수의 경우에 차이가 두드러진다.

 

num = int(input())
from collections import deque

cards = deque(range(1, num+1))

while len(cards) > 1:
    cards.popleft()
    cards.append(cards.popleft())

print(cards[0])


### 시간초과
# cards = [i for i in range(1, num+1)]
#
# while True:
#     if len(cards) != 1:
#         cards.pop(0)
#         cards.append(cards.pop(0))
#     else:
#         print(cards[0])
#         break