★Stack & Queue & Deque Intermediate I - 20 Solved★

★ 10828 스택 ★

 

import sys

N = int(sys.stdin.readline())
stack = []*N
kinds = ['push', 'pop', 'size', 'empty', 'top']

for _ in range(N):
    order = sys.stdin.readline().split()
    kind = order[0]

    if kind == kinds[0]:
        stack.append(order[1])
    
    elif kind == kinds[1]:
        if len(stack) > 0:
            print(stack[-1])
            stack.pop()
        else:
            print(-1)
    
    elif kind == kinds[2]:
        print(len(stack))
    
    elif kind == kinds[3]:
        print(0) if len(stack) > 0 else print(1)

    else:
        print(stack[-1]) if len(stack) > 0 else print(-1)

 

🥦 stack을 list의 형태로 정의했고,삽입은 append, 삭제는 pop method를 사용하였다. 여기서 주어진 N의 길이에 맞는 stack을 미리 할당해 할당 메모리와 소요 시간을 최소화

---

★ 28278 스택 2 ★

 

import sys
input=sys.stdin.readline
N=int(input())
stack=[]
for _ in range(N):
    orders=list(map(int,input().strip().split()))
    if orders[0] == 1:
        stack.append(orders[1])
    elif orders[0] == 2:
        if stack: 
            print(stack.pop())
        else:
            print(-1)
    elif orders[0] == 3:
        print(len(stack))
    elif orders[0] == 4:
        if not stack: print(1)
        else: print(0)
    else:
        if stack: print(stack[-1])
        else: print(-1)

---

★ 9012 괄호 ★

 

def if_VPS(PS):
    stack = []

    for p in PS:

        if stack:
            if stack[-1] == '(' and p == ')':
                stack.pop() 
            else:
                stack.append(p)
        else:
            stack.append(p)
    
    if not stack:
        return 'YES'
    else:
        return 'NO'


for _ in range(int(input())):
    PS = input()

    print(if_VPS(PS))

 

🧜‍♀️ PS에서 한 개씩 stack에 넣되, 기존에 stack에서 '('가 존재한다면, PS에서 빼낸 문자가 ')'일 경우, 서로 매칭되어 없앰. 이렇게 매칭되는 괄호쌍들을 계속 없애며 PS 모든 iteration이 끝난 뒤, stack에 수가 남아있다면 VPS가 아니므로 NO, 없다면 YES

---

★ 5957 Cleaning the Dishes ★

 

import sys
input=sys.stdin.readline
N=int(input())
unwashed=[N-i for i in range(N)]
washed_but_not_dried=[]
washed_and_dried=[]
while 1:
    if len(washed_and_dried)==N: break
    C_i,D_i=map(int,input().split())
    if C_i==1:
        for _ in range(D_i):
            washed_but_not_dried.append(unwashed.pop())
    else:
        for _ in range(D_i):
            washed_and_dried.append(washed_but_not_dried.pop())
print(*washed_and_dried[::-1],sep='\n')

 

🧜‍♀️ 총 3개의 stack을 사용 → unwashed, washed_but_not_dried, washed_and_dried. C_i가 1이면 D_i 개수만큼 unwashed에서 washed_but_not_dried stack으로 옮기고, C_i가 2이면 D_i 개수만큼 washed_but_not_dried에서 washed_and_dried로 옮기기. stack 자료구조의 물리적 위치인 맨 위는 list의 맨 뒤 원소, stack의 물리적 구조상 맨 아래 element는 list의 맨 앞 원소를 뜻한다. stack의 물리적 위치 상 맨 위부터 출력하려면 list의 뒤 원소부터 reversed order로 출력. stack의 위/아래와 list의 맨 앞/뒤 구분만 헷갈리지 x

---

★ 4949 균형잡힌 세상 ★

 

def is_balanced(string):
    stack = []

    for str in string:
        if str in ['(', ')', '[', ']']:
            if stack:
                if (stack[-1] == '(' and str == ')') or (stack[-1] == '[' and str == ']'):
                    stack.pop()
                else:
                    stack.append(str)
            else:
                stack.append(str)
    
    if not stack:
        return 'yes'
    else:
        return 'no'

while 1:
    string = input()

    if string == '.':
        break

    print(is_balanced(string))

 

🧜‍♀️ 위 9012번 문제와 동일

---

★ 10773 제로 ★

 

import sys
input = sys.stdin.readline

st = []
for _ in range(int(input())):
    n = int(input())

    st.pop() if n == 0 else st.append(n)
      
print(sum(st))

 

🧜‍♀️ 0을 부를 때마다 가장 최근의 수를 지우는 방식 - stack 활용 → FIFO(First In First Out)

---

★ 24813 The Grand Adventure ★

 

for _ in range(int(input())):
    adventure_string=input()
    backpack=[]
    flag=0
    for s in adventure_string:
        if s in ['$','|','*']:backpack.append(s)
        elif s in ['b','t','j']:
            if len(backpack)==0:
                print('NO')
                flag+=1
                break
            popped=backpack.pop()
            if (s=='b'and popped!='$') or (s=='t'and popped!='|') or (s=='j'and popped!='*'):
                print('NO')
                flag+=1
                break
    if flag==0:print('YES'if len(backpack)==0 else'NO')

 

🧜‍♀️ 문제에서 bag가 일종의 stack 자료구조 역할을 한다. 최근에 집어넣은 것만 꺼낼 수 있다 했으므로 stack 사용. b라면 꺼낸 게 $가 아니거나, t라면 |, j라면 *가 아닐 경우, 또는 꺼낼 게 없는 경우 - 이 두 가지 if문으로 yes/no 판정

---

★ 3986 좋은 단어 ★

 

import sys
input=sys.stdin.readline

def is_good_word(word):
    stack=[]
    for i in word:
        if len(stack)!=0 and stack[-1]==i:stack.pop()
        else:stack.append(i)
    if len(stack)==0:return True
    else: return False


n=0
for _ in range(int(input())):
    if is_good_word(input().rstrip()):n+=1
print(n)

 

🧜‍♀️ 선을 교차하지 않으면서 동일한 글자끼리 선이 연결된다는 건, stack을 만들어서 pop()과 append() 연산을 모두 진행했을 때 최종적으로 stack에 남는 알파벳이 없는 경우이다. 짝 짓는 유형은 stack을 만들어서 최종적으로 stack에 내용이 남아있는지 아닌지 확인할 때 주로 판단

---

★ 10845 큐 ★

 

from collections import deque
import sys
N = int(sys.stdin.readline())
queue = deque(maxlen=N)
kinds = ['push', 'pop', 'size', 'empty', 'front', 'back']

for _ in range(N):
    order = sys.stdin.readline().split()
    kind = order[0]

    if kind == kinds[0]: #push X
        queue.append(order[1])
    
    elif kind == kinds[1]: #pop
        print(queue.popleft()) if queue else print(-1)
    
    elif kind == kinds[2]: #size
        print(len(queue))
    
    elif kind == kinds[3]: #empty
        print(1) if len(queue) == 0 else print(0)

    elif kind == kinds[4]: #front
        print(queue[0]) if queue else print(-1)

    else: #back
        print(queue[-1]) if queue else print(-1)

 

🥦 deque()의 인자로 maxlen을 미리 설정해 메모리 용량 초과 방지. 성능 속도 빨리 개선. append()와 popleft() 사용. popleft() 출력물이 빼낸 원소 자체값을 리턴. queue 자체가 조건이 되어 원소가 queue 안에 한 개 이상이라도 존재한다면 True, 원소가 없으면 False

---

★ 18258 큐 2 ★

 

import sys
input=sys.stdin.readline
from collections import deque
queue=deque()
N=int(input())

for _ in range(N):
    orders=input().strip().split(' ')
    if orders[0] == 'push': queue.append(orders[1])
    elif orders[0] == 'pop':
        if queue: print(queue.popleft())
        else: print(-1)
    elif orders[0] == 'size':
        print(len(queue))
    elif orders[0] == 'empty':
        if queue: print(0)
        else: print(1)
    elif orders[0] == 'front':
        if queue: print(queue[0])
        else: print(-1)
    else:
        if queue: print(queue[-1])
        else: print(-1)

 

🥦 queue의 맨 왼쪽은 queue[0]으로, queue의 맨 오른쪽 원소는 queue[-1]로 알 수 있다. 맨 왼쪽은 제일 처음에 넣은 원소 / 맨 오른쪽은 제일 최근, 마지막에 넣은 원소. 양 끝의 원소 확인은 O(1)

---

★ 11866 요세푸스 문제 0 ★

+++

★ 1158 요세푸스 문제 ★

 

from collections import deque
import sys
input = sys.stdin.readline

N,K = map(int,input().split())
q = deque([i for i in range(1,N+1)])
l = []

while len(q) != 0:
    for _ in range(K-1):
        q.append(q.popleft())
    l.append(q.popleft())

print('<'+str(l)[1:-1]+'>')

 

🥦 원 순열의 경우 주로 queue. N이 7, K가 3이라면 일단 모든 수를 queue에 집어넣은 뒤, 1번째와 2번째는 다시 queue에 넣고(즉 원이므로 빼내서 순서상 라스트 꼬리에 넣어야 하기에 queue 자료구조가 적당), 3번째는 빼서 정답 list에 넣는다, queue에 존재하지 않을 때까지 이를 반복

---

★ 2164 카드2 ★

 

import sys
from collections import deque

N = int(sys.stdin.readline())
lst = [i for i in range(1,N+1)]
queue = deque(lst)

while len(queue) != 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue[0])

 

🥦 queue를 list 자료구조에서도 사용할 수 있지만, 성능 측면에서 많이 부족하므로 deque()을 많이 활용. list의 pop(0)과 insert(0,x)는 O(N) 하지만 deque의 popleft(), appendleft(x) 모두 O(1)이기에 넣고 빼는 시간이 list에 비해 매우 단축. 하지만, deque의 무작위 접근 시간복잡도는 O(N)이므로 해당 data를 가기까지 계속 iteration이 진행. 먼저 들어온 게 먼저 나가는, 즉, 위에서 빼서 아래로 넣는 문제는 queue 활용. 1개 원소만 남을 때까지 popleft()와 append() 반복 사용

---

★ 1966 프린터 큐 ★

 

from collections import deque
import itertools
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N,M=map(int,input().split())
    order = 0

    #queue 생성
    queue=deque(maxlen=N) #N개가 들어갈 수 있는 queue
    importances=list(map(int,input().split())) #중요도

    for i in range(N):queue.append(importances[i]) #queue에 중요도 집어 넣음

    while queue:
        others = list(itertools.islice(queue, 1, len(queue)))

        if len(others) == 0: #나 하나만 있다면 바로 출력
            order += 1 #인쇄하므로 인쇄 순서 1증가
            print(order)
            break
        
        else:
            if queue[0] >= max(others): #queue의 가장 앞에 있는 문서 인쇄
                M-=1 #원하는 문서 정렬 순서 -1
                order+=1 #인쇄하므로 인쇄 순서 1 증가
                queue.popleft() #인쇄하므로 맨 앞의 문서 빼내기
                if M == -1: #인쇄하는 문서가 원하는 문서라면
                    print(order)
                    break
                
            else: #중요도가 더 높은 문서가 뒤에 존재
                queue.append(queue.popleft()) #맨 앞의 문서를 빼내서 뒤에 붙이기
                M-=1 #원하는 문서 정렬 순서 -1
                if M == -1: #원하는 문서가 맨 뒤로 가게 된다면 해당 문서의 정렬 순서 len(queue)-1로 설정
                    M = len(queue) -1

 

🥦 인쇄를 앞에서부터, 즉 먼저 들어온 문서부터 하려고 하되, 대기 중인 문서들의 중요도보다 모두 높아야 하고, 그렇지 않으면 뒤로 보내는 문제. 내가 원하는 문서의 현재 queue 정렬 순서를 안 상태에서(M)

 

① queue에 문서 1개만 있다면 바로 출력 - order+1 한 다음 order값 출력 - 

 

→ queue에 문서 2개 이상 있다면

② 만약 중요도가 더 높은 문서가 뒤에 없다면, 바로 출력 - 역시 order+1하고, 모든 문서가 왼쪽으로 움직이므로 M 순서 - 1. 이 때 내가 원하는 문서라면(M값이 -1이면) 바로 order값 출력

 

③ 중요도가 더 높은 문서가 뒤에 존재한다면 앞의 문서 빼서 뒤에 붙이는, queue의 append() & popleft() 사용. 이 때 내가 원하는 문서가 뒤로 가게 된다면 M값을 len(queue)-1로 따로 맞춰줌

 

🥦 itertools의 islice()를 이용해 현재 나를 제외, queue에 대기하는 뒤의 모든 문서들만 빼올 수 있음 (인자: 대기열,start,stop,step). 내가 원하는 문서를 queue의 정렬 순서 M이 -1이 되는 지 여부에 따라 판단해 위 세가지 상황에 맞게 code 짜주면 끝!

---

★ 10866 덱 ★

 

from collections import deque
import sys

dq = deque()
input = sys.stdin.readline

for _ in range(int(input())):
    orders = input()
    
    order = orders.split()[0]

    if order == 'push_front':
        dq.appendleft(orders.split()[1])

    elif order == 'push_back':
        dq.append(orders.split()[1])
    
    elif order == 'pop_front':
        if dq:
            print(dq.popleft())
        else:
            print(-1)
    
    elif order == 'pop_back':
        if dq:
            print(dq.pop())
        else:
            print(-1)
    
    elif order == 'size':
        print(len(dq))
    
    elif order == 'empty':
        if dq:
            print(0)
        else:
            print(1)
    
    elif order == 'front':
        if dq:
            print(dq[0])
        else:
            print(-1)
    
    elif order == 'back':
        if dq:
            print(dq[-1])
        else:
            print(-1)

 

🐳 일렬로 되어 있는 deque에서 왼쪽 삽입 appendleft(), 오른쪽에서 삽입 append(), 왼쪽에서 빼내기 popleft(), 오른쪽에서 빼내기 pop()

---

★ 28279 덱 2 ★

 

import sys
input=sys.stdin.readline
from collections import deque
dq=deque()
for _ in range(int(input())):
    order=input().rstrip().split()
    if order[0] == '1':
        dq.appendleft(order[1])
    elif order[0] == '2':
        dq.append(order[1])
    elif order[0] == '3':
        if dq:
            print(dq.popleft())
        else:
            print(-1)
    elif order[0] == '4':
        if dq:
            print(dq.pop())
        else:
            print(-1)
    elif order[0] == '5':
        print(len(dq))
    elif order[0] == '6':
        if dq: print(0)
        else: print(1)
    elif order[0] == '7':
        if dq:
            print(dq[0])
        else:
            print(-1)
    elif order[0] == '8':
        if dq:
            print(dq[-1])
        else:
            print(-1)

 

🐳 deque은 제일 앞/뒤 원소 확인 O(1) 

---

 

★ 20301 반전 요세푸스 ★

 

from collections import deque
N,K,M=map(int,input().split())
dq = deque(i for i in range(1,N+1))
reverse=0
while 1:
    if len(dq)==0: break
    if reverse==0: #요세푸스
        cnt=0
        while dq:
            for _ in range(K-1):
                dq.append(dq.popleft())
            print(dq.popleft())
            cnt+=1

            if cnt==M:
                reverse+=1
                break

    if reverse==1: #반전 요세푸스
        cnt=0
        while dq:
            for _ in range(K-1):
                dq.appendleft(dq.pop())
            print(dq.pop())
            cnt+=1

            if cnt==M:
                reverse-=1
                break

 

🐳 요세푸스 순열은 circular 원에서 queue 방식으로 왼쪽에서 popleft()를 진행하고, target이 아니면 오른쪽으로 append()하는 방식. 그러나 반전 요세푸스 순열은 그 반대로 회전하기 때문에 오른쪽에서 pop()을 진행하고, target이 아니면 왼쪽으로 appendleft() / counting 변수로 M에 도달하면 요세푸스 순열대로 진행할 지, 반전 요세푸스 순열대로 진행할지 판단. 상황에 따라 양쪽에서 append, pop을 자유자재로 진행해야 하므로 자료구조 deque이 적당

---

★ 17952 과제는 끝나지 않아! ★

 

import sys
input=sys.stdin.readline

N=int(input())
t,stack=0,[]
for _ in range(N):
    info=list(map(int,input().split()))
    if info[0]==1:
        if info[2]==1: t+=info[1]
        else:
            stack.append([info[1],info[2]-1])
    else:
        if stack:
            stack[-1][1] -= 1
            if stack[-1][1] == 0:
                t+=(stack.pop()[0])
print(t)

 

🐳 최근 과제부터 먼저 해결하므로 스택 자료구조 활용. 1이면 새롭게 나온 과제 처리 / 0이면 stack에 최근에 들어간 과제 1분 처리

---

★ 17891 Pairing Socks ★

 

import sys
input=sys.stdin.readline
n=int(input())
org=list(map(int, input().split()))
aux,cnt=[],0

for x in org:
    cnt+=1
    if aux:
        if x != aux[-1]:
            aux.append(x)
        else:
            aux.pop()
    else:
        aux.append(x)
if aux:
    print('impossible')
else:
    print(cnt)

 

🐳

→ 쌓여있는 org for loop 돌기

→ 오른쪽 aux stack에 아무것도 없다면 aux 쌓기 / 있다면 aux 맨 위 원소와 org의 맨 위 원소 비교: 같다면 pop(), 다르다면 오른쪽 aux 쌓기

 

※ 위 2번 move는 필요 x. pair를 구하는 경우는 양 stack의 꼭대기 sock과의 비교이므로 굳이 2번 move 없이 1번 move만으로 충분. 따라서 org for loop 돌리면 되고 possible한 case라면 len(org)가 정답. 양 쪽이 뚫려있지 않은, 한 쪽만 뚫린 stack의 구조 상 비교가 제한적으로 이루어져 쉽게 풀 수 있었던 문제

---

★ 4540 Q ★

 

import sys
input=sys.stdin.readline
from collections import deque

for _ in range(int(input())):
    m,n=map(int,input().split())
    l=list(input().split())
    dq=deque(l)
    ans=['?']*m
    for _ in range(n):
        x,y=map(int,input().split())
        dq.remove(l[x-1])
        ans[y-1]=l[x-1]
    for i in range(m):
        if ans[i] == '?':
            ans[i] = dq.popleft()
    print(*ans)

 

🐳 먼저 지정 위치에 일부 원소를 넣고 나머지는 queue 돌리며 popleft()한 결과 차곡차곡 넣기

---