[python] deque

1. deque

: stack이나 queue처럼 한 방향이 아닌(병 모양), 양 쪽에서 삽입 삭제가 가능한 자료구조(파이프 모양)

 

자료 입출력 관점에서 봤을 때, 0번 위치에 value를 삽입/삭제 시

• List는 index를 모두 재배치해주어야 하기 때문에 시간복잡도 O(N)이 소모된다.
• 반면 deque는 O(1)의 시간복잡도를 가져 월등히 빠르다

from collections import deque

 

 

2. deque의 특징

• FIFO(First In First Out): 파이프 구조
• list보다 엄격
• list보다 빠른 속도
• 인덱싱은 가능, But slicing을 불가!

 

3. deque의 method

list의 method는 거의 다 사용 가능하나(.append(), .pop() 등), 특징적인 method가 있다.

• appendleft : 왼쪽에 개체를 추가(O(1))
• extendleft : 왼쪽에 리스트를 연장
• maxlen : 큐의 길이를 반환
• popleft : 큐의 맨 왼쪽에 있는 개체를 반환(O(1)) (= list.pop(0), O(N))
• rotate : 큐를 회전합니다(컨테이너 벨트처럼 밀어서 회전).

d = deque([1, 2, 3, 4, 5])

d.rotate(2)
print(d)

d.rotate(-2)
print(d)

deque([4, 5, 1, 2, 3])
deque([1, 2, 3, 4, 5])

 

 

4. 문제

1) 2164번 카드2

  N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래 오도록 정렬되어 있다. 정렬된 카드 중 제일 위에 있는 카드를 바닥에 버리고, 남은 카드 중 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮기는 작업을 반복한다.

 

  이때, 제일 마지막까지 남아있는 카드의 값은 무엇일까?

# 0:나의 풀이
##2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
##2 2 4 2 4 6 8 2  4  6  8 10 12 14 16
import math

inputted = int(input())
num_square = int(math.log2(inputted))
## inputted - 2**num_square = num_mul
num_mul = inputted - 2**num_square
## 2 * num_mul = 마지막수
last_num = 2 * num_mul

print(last_num if num_mul != 0 else inputted)



# 1: deque를 이용한 풀이
from collections import deque

N = int(input())
deque = deque([i for i in range(1, N+1)])

while(len(deque) >1):
    deque.popleft()
    deque.append(deque.popleft())
    
print(deque[0])



# 2: list splicing을 이용한 풀이 
n = int(input())
l = list(range(1,n+1))
while True:
    if len(l)%2==0:
        l = l[1::2]
    else:
        l = [l[-1]]+l[1::2]
    if len(l)==1:
        break    
        
print(l[0])

 

2) 1966번 프린터큐

#0
import sys

num = int(sys.stdin.readline())
    
for _ in range(num):
    n, m = map(int, sys.stdin.readline().split())    
    arr = list(enumerate(map(int, sys.stdin.readline().split())))
    check = arr[m] # tuple 전체로 체크 가능
    idx = 0

    while arr:
        max_arr = max([i[1] for i in arr]) # 길면 시간초과 가능성 있음
        if arr[0][1] == max_arr: # 최대 일 때 pop -> 제거
            now = arr.pop(0)
            idx += 1
            if now == check:
                print(idx)
                break
        else:
            arr.append(arr.pop(0))

#1
round = int(input())

for _ in range(round):
    n, m = map(int, input().split())
    li = list(map(int, input().split()))
    cnt = 1
    while li:
        if li[0] < max(li): # 1) 현재 문서보다 우선순위 높은 게 뒤에 있는 경우
            li.append(li.pop(0))
        else:
            if m == 0: # 2) 현재 문서가 타겟 문서인 경우 (인쇄 후 종료)
                break  
            li.pop(0)  # 3) 현재 문서가 가장 우선순위가 높은 경우 (삭제)
            cnt += 1       
        m = (m - 1) if (m > 0) else (len(li) - 1) # 1/3)에서 모두 실행
        # 경우1. 앞 문서 한 칸 제거 -> 관심문서 한 칸 당김
        # 경우2. m==0인 경우 - 관심문서 pop할 차례
        # 경우3. 관심문서인데 중요도 때문에 뒤로 밀림 -> 맨 뒤로 위치 갱신
        #        (if와 m 조건문을 계속 돌며 action은 else의 pop에서 발생)
    
    print(cnt)

 

• 취해야 할 action과 실질적 result를 분리할 것
• 정렬과 자료구조가 머릿속에서 명확하지 않아 문제 풀이 시간이 오래걸리는 것 같다는 느낌을 이번 문제에서 받았다.

 

 

 

 

 

 

 

 

 

 

참고문헌

[파이썬 모듈 collections] deque 큐의 이해, 사용법