[python] deque

백준 2346 풍선 터뜨리기 문제를 풀면서 deque의 rotate 함수를 사용해보았다.

사실 deque를 사용하면서 주로 popleft() 밖에 사용하지 않아서 rotate라는 함수가 있는 줄도 몰랐다..
그래서 한 번 deque에 대해서 정리해보려고 한다 후후..

Deque, Double-ended Queue

deque는 내부적으로 double-linked list로 구현되어있다.

주요 함수로는

• append()
• appendleft()
• pop()
• popleft()
  가 있는데, append()와 pop()은 list와 동일하게 작동한다.

appendleft()와 popleft()는 deque가 double-linked list로 구현되어 있어 시간복잡도 O(1)을 만족하면서 작동한다.

rotate()

풍선 터뜨리기 문제를 풀면서 사용한 rotate() 함수에 대해서 알아보자.

q.rotate(num)

num이 양수일 때는 시계방향으로,
음수일 때는 반시계방향으로 회전시킨다.

deque의 rotate()를 사용해서 푼 풍선 터뜨리기 코드!

from collections import deque


n = int(input())
q = deque(enumerate(map(int,input().split())))
answer=[]

while q:
  idx, num = q.popleft()
  answer.append(idx+1)
  if num>0:
    q.rotate(-(num-1))
  else:
    q.rotate(-num)

print(' '.join(map(str,answer)))