백준 2164 (deque) 파이썬

https://www.acmicpc.net/problem/2164

2164번: 카드2

---

코드

from collections import deque
n = int(input())
box = deque()
count = 0
for i in range (n):
    box.append(i + 1)
while len(box) != 1:
    count += 1
    if count % 2 == 1:
        box.popleft()
    else:
        box.append(box.popleft())
print(box[0])

---

풀이

 

처음 문제 풀 때에는 간단하게 요소를 삭제할 때에는 box.pop()을 이용하고,  맨 앞 원소를 맨 뒤로 옮기는 작업은 box.append(box.pop(0))을 이용했다. 하지만 코드를 제출하니 시간 초과가 떠버렸다. 

 

검색을 해보니 deque를 이용해서 풀면 되는것이었다. deque는 double ended queue의 약자이며 큐와 스택을 둘 다 만들 수 있는 자료구조이다. 그리고 양 끝단에서 모두 push와 pop이 가능하다. 특히 파이썬에서 collections 모듈 안의 deque는 속도면에서 훨씬 빠르기 때문에, 알고리즘 문제를 풀 때에는 보통 deque를 많이 사용한다고 하니 익숙해지도록 하자.