✏️ 1. 들어가며

이 문제는 collections 라이브러리 내의

deque 클래스를 이용하여

queue 를 구현하는 문제였습니다.

deque 클래스 사용법은 아래와 같습니다.

from collections import deque

queue = deque()

queue.append(1) # 오른쪽 원소 추가  [1]
queue.appendleft(2) # 왼쪽 원소 추가 [2, 1]
queue.appendleft(3) # 왼쪽 원소 추가 [3, 2, 1]

queue.pop() # 오른쪽 원소 제거  [3, 2]
queue.popleft() # 왼쪽 원소 제거 [2]

✏️ 2. 수도코드 작성

while (카드가 한 장 남을 때까지)
    1. 제일 위에 있는 카드를 버리고
    2. 그 다음 카드를 제일 뒤로 옮긴다.
반복문 종료 후 남은 카드에 적힌 숫자출력

✏️ 3. 정답코드 작성

import sys
from collections import deque

input = sys.stdin.readline

N= int(input())

queue = deque(range(1,N+1))

while len(queue) > 1 :
    queue.popleft()
    next_val = queue.popleft()
    queue.append(next_val)

print(queue[0])

✏️ 4. 배운 점

# deque는 파이썬 list에 비해 
# 제일 앞의 원소 제거 시에 유리합니다. 

list.pop(0) # 시간복잡도 n
deque.popleft() # 시간복잡도 1