최대 1 분 소요

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 값만 조정됨

    자료 출처: python documents