[큐/Python] 2164번: 카드2 - 효과는 굉장했다!

2164번: 카드2

 

알고리즘 분류

• 자료 구조
• 큐

 

 

SOLUTION

import sys
from collections import deque

N = int(sys.stdin.readline())
deque =  deque([i for i in range(1,N+1)]) 

while(len(deque) > 1):
    deque.popleft() # 카드에서 가장위에 있는 수 버림
    deque.rotate(-1) # rotate()함수를 이용해 deque안에 있는 값들을 왼쪽으로 한칸씩 이동 0번째 인덱스에 있는 값은 가장 마지막 인덱스로 이동

print(deque[0])

※ pop(0) vs popleft()

 사실 기능적인 측면으로만 봤을 때 둘의 기능은 같다.

그러나 시간복잡도를 비교 해보면 pop(0)의 시간복잡도는 O(N) 이고 popleft()의 시간복잡도는 O(1)이기 때문에, deque의 popleft()를 쓰는게 더 효율적인 코드라고 볼 수 있다.

 

※ collections.deque

collections — Container datatypes — Python 3.10.0 documentation