[백준 2164] 카드 2
2164번 : 카드 2
방법 1
import sys
from collections import deque
n = int(input())
cards = deque(list(i for i in range(1, n+1)))
# 카드가 한 장 남으면 종료
while len(cards) > 1:
# 제일 위에 있는 카드를 버린다
cards.popleft()
# 제일 위에 있는 카드를 제일 뒤로
cards.append(cards.popleft())
print(cards[0])
pop(0) vs popleft
pop(0)
- list 자료형의 method: pop
- list에서 주어진 위치에 있는 항목을 삭제하고, 그 항목을 돌려준다.
-
list의 끝(index: -1)에서 append / pop 하는 것은 O(1) 시간 걸리지만,
머리(index: 0)에 append / pop 하는 것은 O(n) 시간 걸린다.
- queue를 구현하려면, 양 끝에서의 덧붙이기와 꺼내기가 모두 빠르도록 설계된 collections.deque를 사용하는 것이 좋다.
popleft
- deque 객체의 method: popleft
-
양쪽 끝에서의 append 와 pop을 O(1) 성능으로 지원 - 원소를 일일히 옮기는 list와 달리, front/rear 값만 조정됨