[백준: 큐, 덱] 18258, 2164, 11866,1966, 10866, 1021, 5430번 문제

큐: 선입선출 자료구조. 스트리밍, 너비 우선 탐색 등에서 쓰임.

파이썬에서 큐 자료구조 사용하기
1. list의 pop(0) 함수 사용하기 (뒤로 데이터를 붙였을 경우) : 시간복잡도 O(N). 데이터를 넣기 전에 기존 데이터들을 쉬프트 해줘야 하기 때문에 비효율적이다.
2. collections 모듈의 deque 사용하기 :
-from collections import deque
-double ended queue의 약자. 데이터를 양방향에서 추가하고 제거할 수 있다.
-popleft() 함수로 첫번째 데이터를 제거한다. 데이터는 뒤쪽으로 들어와서 앞쪽으로 나가는 형식이다. 추가시 append()함수 이용
-appendleft(a) 함수 사용시 데이터는 맨 앞쪽에 들어가고, 데이터 흐름이 앞쪽에서 들어오고 뒤쪽으로 나가는 형식이 된다. 제거시 pop()함수 이용.
3. queue모듈의 Queue 객체 시용하기:
-from queue import Queue
-put(a), get()만 이용

[백준 18258 문제 : 큐2]

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

import sys
from collections import deque

n = int(sys.stdin.readline())
dq = deque([])

for _ in range(n):
    temp = list(sys.stdin.readline().split())
    if len(temp)==2 : #push 숫자 경우
        dq.append(int(temp[1]))
    elif temp[0]=="pop":
        if dq : print(dq.popleft()) #큐 비어있지 않은경우
        else : print(-1) #큐 비어있는경우
    elif temp[0]=="size":
        print(len(dq))
    elif temp[0]=="empty":
        if dq : print(0)
        else : print(1) #비어있는 경우
    elif temp[0]=="front":
        if dq : print(dq[0])
        else : print(-1)
    elif temp[0]=="back" :
        if dq : print(dq[-1])
        else : print(-1)

[백준 2164 문제 : 카드2]

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

import sys
from collections import deque

n = int(sys.stdin.readline())
dq=deque([])

for i in range(1,n+1): # 숫자 집어 넣기
    dq.append(i)

while len(dq)>1 :
    dq.popleft() #맨 윗장 버리기 (1 버리기)
    dq.append(dq.popleft()) #다음 윗장을 아래로 (2를 아래로)

print(dq.pop()) #마지막 한장

[백준 11866 문제 : 요세푸스 문제0]

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

import sys

n, k = map(int, sys.stdin.readline().split())

queue = [] #리스트를 큐로 활용

for i in range(1,n+1):
    queue.append(i)

count = 1 #2일때 사람 지울거임
yose = []
index = 0
while queue : 
    if count%k==0: #k번째 사람 제거
        yose.append(str(queue.pop(index)))
        index-=1 #큐의 길이가 줄어들어 인덱스 변화
    count+=1
    index+=1
    
    if index>len(queue)-1 :
        index = 0

print('<'+', '.join(yose)+'>') #조인은 String 리스트만 가능

[백준 1966 문제 : 프린터 큐]

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


시간초과 난 코드:

import sys
from collections import deque

testCaseN = int(sys.stdin.readline())

for _ in range(testCaseN):
    flag = False
    count = 0
    #N:문서의 수 M:궁금한 문서 현재 위치
    N,M = map(int,sys.stdin.readline().split())
    #문서들의 중요도
    priorities = deque(list(map(int,sys.stdin.readline().split())))

    if len(priorities)==1 : #문서가 하나뿐이면 프린트
        count+=1
        print(count)
        continue
    
    while priorities :
        if flag : break

        for i in range(1,len(priorities)) :
            #우선순위가 맨 앞보다 큰 것이 있으면 뒤로 보내기
            if priorities[0]<priorities[i] :
                priorities.append(priorities.popleft())
                #궁금한 문서의 위치 변경
                if M==0 : M=len(priorities)-1  
                else : M-=1 
                break
            
            #마지막까지 검사했는데 큰 것 없으면 맨 앞 문서 프린트
            if i == len(priorities)-1:
                count+=1 #인쇄 카운트 증가
                if M==0 : #만약 M이 맨 앞이었으면 끝
                    print(count) 
                    flag=True #while문 빠져나가는 용

                else :
                    priorities.popleft()
                    #궁금한 문서의 위치 변경
                    if M==0 : M=len(priorities)-1  
                    else : M-=1 
                break

max함수를 사용하여 비교하니 시간초과 해결

import sys
from collections import deque

testCaseN = int(sys.stdin.readline())

for _ in range(testCaseN):
    flag = False
    count = 0
    #N:문서의 수 M:궁금한 문서 현재 위치
    N,M = map(int,sys.stdin.readline().split())
    #문서들의 중요도
    priorities = deque(list(map(int,sys.stdin.readline().split())))

    if len(priorities)==1 : #문서가 하나뿐이면 프린트
        count+=1
        print(count)
        continue
    
    while priorities :
        if flag : break
        #print("max"+str(max(priorities)))

        if priorities[0]<max(priorities) :
            priorities.append(priorities.popleft())
            #궁금한 문서의 위치 변경
            if M==0 : M=len(priorities)-1  
            else : M-=1 
        else : 
            count+=1
            if M==0 : #만약 M이 맨 앞이었으면 끝
                print(count) 
                flag=True #while문 빠져나가는 용

            else :
                priorities.popleft()
                #궁금한 문서의 위치 변경
                if M==0 : M=len(priorities)-1  
                else : M-=1 

[백준 10866 문제 : 덱]

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

import sys
from collections import deque
def dequeue(dq):
    inputList = list(sys.stdin.readline().split())
    
    if len(inputList)==2 :
        if inputList[0]=="push_front":
            dq.appendleft(inputList[1]) #덱의 앞에 넣기
        elif inputList[0]=="push_back":
            dq.append(inputList[1])
            
    else :
        if inputList[0]=="size":
            print(len(dq))
        elif inputList[0]=="empty":
            if dq : print(0)
            else: print(1)
        elif inputList[0]=="front":
            if dq : print(dq[0])
            else : print(-1)
        elif inputList[0]=="back":
            if dq : print(dq[-1])
            else: print(-1)
        elif inputList[0]=="pop_front":
            if dq : print(dq.popleft()) #앞 수 빼고 출력
            else : print(-1)
        elif inputList[0]=="pop_back":
            if dq : print(dq.pop()) #맨 뒤 빼고 출력
            else : print(-1)

n = int(sys.stdin.readline())
dq = deque()

for _ in range(n) :
    dequeue(dq)

if dq is None 은 왜 안 되는걸까?

[백준 1021 문제 : 회전하는 큐]

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

from collections import deque
import math
import sys

#N:큐의 크기  M:뽑아내려는 수의 개수
N,M = map(int, sys.stdin.readline().split())

#뽑아내려는 수의 위치
nums = list(map(int,sys.stdin.readline().split()))
numsDq = deque(nums)

dequeue = deque()
for i in range (1, N+1) :
    dequeue.append(i) #[1,2,3,4...,N]

nIndex = 0 #nums 인덱스용
count = 0 #연산 카운트용
while numsDq :
    #뽑아내려는 수가 앞에 있으면 뽑아내기
    if numsDq[0]==dequeue[0]: 
        dequeue.popleft()
        numsDq.popleft()
    
    else : 
        indexFind = 0 #빼려는 수 현재 위치 인덱스
        for i in range(len(dequeue)) :
            if dequeue[i]==numsDq[0] :
                indexFind = i
                break
        
        if indexFind<=math.floor(len(dequeue)/2):
            #왼쪽으로 밀기. 뽑을 수 맨 앞으로 보내기
            for _ in range(indexFind) :
                dequeue.append(dequeue.popleft())
                count+=1                
            dequeue.popleft() #뽑기
            numsDq.popleft()
        
        else : # 오늘쪽으로 밀기
            for _ in range(len(dequeue)-indexFind):
                dequeue.appendleft(dequeue.pop())
                count+=1
            dequeue.popleft() #뽑으려는 수 뽑음
            numsDq.popleft()

print(count)

[백준 5430 문제 : AC]

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

from collections import deque

def R(flag): #뒤집는 함수
    #True 앞으로 나가고 뒤로 들어오는 방향
    #False 뒤로 나가고 앞으로 들어오는 방향 
    if flag : flag = False
    else : flag= True
    return flag

def D(dequeue,flag): #첫번째 버리는 함수
    if flag: # 앞으로 나가고 뒤로 들어오는 방향
        dequeue.popleft()
    else :
        dequeue.pop()
    return dequeue 



n = int(input())
for _ in range(n):
    functions = input()
    m = int(input())
    if m!=0 :
        nums = list(input().split("[")[1].split("]")[0].split(","))
    else : #[]로 입력이 들어올경우 ['']리스트가 되어 따로 해줘야함
        input()
        nums = []
    dequeue = deque(nums)
    flag = True # 방향용
    isError = False
    #print("+++"+str(dequeue))
    
    for fun in functions :
        if fun == "R" :
            flag = R(flag)
        elif fun =="D" :
            if dequeue :
                dequeue = D(dequeue,flag)
            else :
                isError = True
                break

    if isError :
        print("error")
    else :
        if flag :
            print("["+','.join(list(dequeue))+"]")
        else :
            temp = list(dequeue)
            temp.reverse()
            print("["+','.join(list(temp))+"]")
                

print(dequeue)를 하면 [1, 2, 3] 으로 나와서 틀린다.
[1,2,3]으로 공백이 없게 프린트 해야 한다.