[BOJ] Queue, DeQue/ 19단계

1	18258	큐 2	성공	7886	26220	30.958%
큐의 개념을 익히고 실습하는 문제. 연산 당 시간 복잡도가 O(1)이어야 한다는 점에 유의하세요.

def push(num) :
    list.append(num)

def pop() :
    if len(list) != 0 :
       print(list.popleft())
    else :
        print(-1)
def size() :
    print(len(list))

def empty() :
    if len(list) != 0 :
        print(0)
    else :
        print(1)

def front() :
    if len(list) != 0 :
        print(list[0])
    else : print(-1)

def back() :
    if len(list) != 0 :
        print(list[-1])
    else :
        print(-1)

import sys 
from collections import deque

list = deque([])
for i in range(int(sys.stdin.readline())) :
    x = sys.stdin.readline().split()
    if x[0] == 'push' :
        push(x[1])
    elif x[0] =='pop' :
        pop()
    elif x[0] == 'size' :
        size()
    elif x[0] == 'empty' :
        empty()
    elif x[0] == 'front' :
        front()
    else :
        back()

---

 

2	2164	카드2	성공	15599	29699	53.860%
큐를 사용하여 동작을 구현하는 문제

from collections import deque
import sys

n = int(sys.stdin.readline())
array = deque()
for i in range(n) :
    array.append(i+1)

while len(array) != 1 :
    array.popleft()
    temp = array.popleft()
    array.append(temp)

print(array.pop())

---

3	11866	요세푸스 문제 0	성공	13135	23039	57.841%
큐를 이용해 제거 과정을 구현하는 문제

import sys 
from collections import deque

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

for i in range(n) :
    array.append(i+1)
    
print("<", end='')

while array :
    for i in range(k-1) :
        array.append(array[0])
        array.popleft()
    
    print("{}".format(array.popleft()), end='')
    if array :
        print(", ",end='')

print(">")

---

4	1966	프린터 큐	성공출처다국어	17461	32210	55.895%
큐의 개념이 응용된 문제

import sys
from collections import deque


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

for _ in range(t) :
    n, m = map(int,sys.stdin.readline().split())
    #array = deque()
    array = deque(list(map(int, sys.stdin.readline().split())))
    index = deque(list(range(len(array))))

    index[m] = -1 #타겟을 -1로 설정
    count= 0
    
    while True:
        if array[0] != max(array) :
            array.append(array[0])
            array.popleft()
            index.append(index[0])
            index.popleft()
            
        else :
            count += 1
            if index[0] == -1 :
                print(count)
                break
            else :
                array.popleft()
                index.popleft()

---

5	10866	덱	성공	16126	29856	56.452%
덱의 개념을 익히고 실습하는 문제. (입력 크기가 너무 작아서 비효율적인 구현으로도 통과가 되지만, 가급적이면 연산 당 시간 복잡도가 O(1)이도록 구현해 주세요.)

import sys
import collections

T = int(sys.stdin.readline())
array = collections.deque([])

for _ in range(T) :
    x = sys.stdin.readline().split()
    if x[0] == "push_front" :
        array.append(x[1])
    elif x[0] == "push_back" :
        array.appendleft(x[1])
    elif x[0] == "pop_front" :
        if len(array) != 0 :
            print(array.pop())
        else :
            print(-1)
    elif x[0] == "pop_back" :
        if len(array) != 0 :
            print(array.popleft())
        else :
            print(-1)
    elif x[0] == "size" :
        print(len(array))
    elif x[0] == "empty" :
        if len(array) != 0 :
            print(0)
        else :
            print(1)
    elif x[0] == "front" :
        if len(array) != 0 :
            print(array[-1])
        else:
            print(-1)
    else :
        if len(array) != 0 :
            print(array[0])     
        else :
            print(-1)

---

6	1021	회전하는 큐	성공출처	10854	20657	54.086%
덱을 활용하여 큐를 회전시키는 문제

import sys
import collections 

def first() :
    array.popleft()

def second() :
    global count
    temp = array.popleft()
    array.append(temp)
    count += 1

def third() :
    global count
    temp = array.pop()
    array.appendleft(temp)
    count += 1
    
count = 0

n, m = map(int, sys.stdin.readline().split())
sequnceArray = list(map(int, sys.stdin.readline().split()))

array = collections.deque(_ for _ in range(1,n+1))

for i in sequnceArray :
    while i != array[0] :
        if array.index(i) < len(array)/2 :
            second()
        else :
            third()
    first()

print(count)

---

7	5430	AC	성공출처다국어	10243	45928	20.242%
덱을 활용하여 시간복잡도를 향상시키는 문제

import sys
import collections

for _ in range(int(sys.stdin.readline())) :
    FuncArray = sys.stdin.readline() #RDD
    n = int(sys.stdin.readline()) #4
    inputArray = sys.stdin.readline()[1:-2].split(",") #1,2,3,4
    if inputArray[0] != '' :
        deque = collections.deque(inputArray) # deque[1,2,3,4]
    else :
        deque = collections.deque()

    
    leftcount= 0
    rightcount = 0
    error = False
    TF = True #TF == True > 리버스x,  TF == False > 리버스ㅇ

    for i in FuncArray : # i == R or D
        
        if i == 'R' : #리버스
            if TF == True : TF = False
            else : TF = True

        elif i == 'D' : #Drop
            if  len(deque) == 0 : #요소가 없으면
                error = True  #error 출력하고 리셋
                break
            else :
                if TF == True :
                    #leftcount +=1
                    deque.popleft()
                elif TF == False :
                    #rightcount +=1
                    deque.pop()

    if FuncArray.count('R') %2 != 0 : # 리버스가 홀수면 
        deque.reverse()

    if error :
        print("error")
    else :
        print("[",end="")
        for i in range(len(deque)):
            print(deque[i],end="")
            if i != len(deque)-1:
                print(",",end="")
        print("]")