BOJ 카드2

import sys
from collections import deque

n = int(sys.stdin.readline())
queue = deque()

for i in range(1, n+1):
    queue.append(i)
# print(queue)

while True:
    if len(queue) ==1:
        print(queue.popleft())
        break
    queue.popleft()
    x = queue.popleft()
    queue.append(x)
    #print(queue)

참고

python에서 시간 복잡도 비교
list 추가/삭제 시간 복잡도 : O(n)

• list는 array로 구현되어있기때문에, 첫번째 원소삭제시 모든 원소를 이동 시키게됨
• fixed size memory blocks(array)

deque 추가/삭제 시간 복잡도 : O(1)

• 링크드 리스트로 구성되어있어서, 포인터로 되있는 연결을 끊으면 끝이남

https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c#l21