★Stack & Queue & Deque Upper-Intermediate I - 12 Solved★

★ 1874 스택 수열 ★

 

import sys
input = sys.stdin.readline

stack,sequence,ans = [],[],[]
cur = 0

for _ in range(int(input())):
    sequence.append(int(input()))

sequence = sequence[::-1]

while len(sequence) != 0:
    popped = sequence.pop()
    if popped > cur:
        for i in range(cur+1,popped+1):
            stack.append(i)
            ans.append('+')
        cur = popped
    
    if popped == stack[-1]:
        stack.pop()
        ans.append('-')
    else:
        ans = []
        break

if len(ans) != 0:
    for i in ans:
        print(i)
else:
    print('NO')

 

 

🫶 주어진 stack에 입력한 수의 순서대로 수열을 만들 수 있는 지 묻는 문제. 4가 먼저 들어가 있으므로 1 - 2 - 3 - 4 차례대로 push. (push하려면 반드시 오름차순을 지켜야 한다) 그 다음 push된 stack에서 pop하면 해당 pop된 원소(popped)가 수열의 원소. 위 1-2 과정을 반복하되, pop된 결과가 원하고자 하는 수열의 순서대로 나오지 않는다면, 수열을 만들 수 없고 NO 출력. 문제에서 주어진 대로 push / pop 구현만 잘하면 됨.

---

★ 4889 안정적인 문자열 ★

 

import sys
input=sys.stdin.readline

num=0
while 1:
    num+=1
    left,right=0,0
    parentheses=input().strip()
    stack=[]
    if '-' in parentheses:break

    #stack operation
    for p in parentheses:
        if len(stack)!=0:
            if p=='}' and stack[-1]=='{':stack.pop()
            else:stack.append(p)
        else: stack.append(p)
    
    if len(stack)==0:print(f'{num}. 0')
    
    else:
        left=stack.count('{')
        right=stack.count('}')
        
        if left==0:print(f'{num}. {(right//2)}')
        
        elif right==0:print(f'{num}. {(left//2)}')
        
        else:
            if left%2==1:print(f'{num}. {(left//2 + right//2 + 2)}')
            else:print(f'{num}. {(left//2 + right//2)}')

 

🫶 안정적인 문자열임을 확인할 때 stack을 을 활용하는 전형적인 stack 문제 유형. 'pair를 형성하는지 확인 - pair간의 결합 결과 원하는 대로 형성되는 지 확인' 대로 그대로 stack으로 검사해주면 된다. 추가로, 만약 stack에 소괄호가 남았을 경우, 무조건 짝수 개수로 남게 되고, { 나 } 한 종류만 남았다면 2로 나눈 몫이 최소 바꾸는 횟수 + {와 }가 같이 혼합되어 있다면, 각각 홀수 개수일 경우 각각의 2로 나눈 몫을 서로 더하고, }와 {가 남으므로 각각 {와 }로 바꿔주는 연산 횟수 2를 더해주면 된다 / 각각 짝수 개수일 경우, 각각의 2로 나눈 몫만 더해주면 된다.(case에 따라 최소 연산의 수 고려) 

---

★ 1406 에디터 ★

 

import sys
input=sys.stdin.readline

#queue
from collections import deque

x=deque(input().rstrip())
y=deque([])
for _ in range(int(input())):
    ord=input().split()
    if ord[0] == 'P':
        x.append(ord[1])
    elif ord[0] == 'L':
        if x:
            y.appendleft(x.pop())
    elif ord[0] == 'D':
        if y:
            x.append(y.popleft())
    else: #B
        if x:
            x.pop()
print(*(x+y),sep='')

 

🫶 커서를 앞뒤로 옮기는 문제를 커서를 고정하고 커서 앞과 뒤에 2개의 deque이 있는 idea로 생각할 수 있는 문제. 커서를 왼쪽으로 한 칸 옮기는 건 왼쪽 deque을 pop해 오른쪽 deque에 appendleft. 커서를 오른쪽으로 한 칸 옮기는 건 오른쪽 deque을 popleft해 왼쪽 deque에 append. 커서 왼쪽에 있는 문자 삭제는 왼쪽 deque pop. 커서 왼쪽에 문자 추가는 왼쪽 deque append. 이 때 pop(), popleft() 때 deque에 원소가 없는 지 있는 지만 여부 확인. 

---

★ 5397 키로거 ★

 

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

for _ in range(int(input())):
    string=input().rstrip()
    x,y=deque(),deque()
    for s in string:
        if s == '<':
            if x:
                y.appendleft(x.pop())
        elif s == '>':
            if y:
                x.append(y.popleft())
        elif s == '-':
            if x:
                x.pop()
        else:
            x.append(s)
    print(*(x+y),sep='')

 

🫶 위 1406 에디터 idea 발상과 동일한 문제. deque 대신 stack 2개 활용도 가능. 다만 나중에 출력 시 입구/출구 구별해서 stack reverse 주의

---

★ 26111 Parentheses Tree ★

 

import sys
input=sys.stdin.readline
parentheses,stack=input(),[]
ans=0
flag=False
for p in parentheses:
    if not stack: stack.append(p)
    else:
        if p=='(':
            stack.append(p)
            flag=True
        else: #')'
            stack.pop()
            if flag: 
                ans += len(stack)
                flag=False

        
print(ans)

🫶 ( 만날 때 stack에 넣고 ) 만날 때 이미 앞에 바로 (가 있었다면 해당 ( 없애고 현재  stack에 들어간 (의 개수 카운트. 위 점선 원만 카운트하므로 더해지는 숫자는 위의 ( 개수. 이는 곧 len(stack). 화살표 순서대로 stack에 append(), pop() 반복

---

★ 6105 Look Up ★

 

#monotone stack
import sys
input=sys.stdin.readline

N=int(input())
stack=[]
ans=[0]*(N+1)
for i in range(1,N+1):
    n=int(input())
    while stack:
        if stack[-1][1]<n:
            popped = stack.pop()
            ans[popped[0]]=i
        else:
            break
    stack.append((i,n))
print(*ans[1:],sep='\n')

 

🫶 스택 기준 계속 들어오는 숫자 중 가장 먼저 나보다 높은 숫자를 가지는 소의 index를 모든 소마다 구하는 문제. 이는 스택 <모노톤 스택> 을 활용해서 구할 수 있다. 이는 스택의 내림차순을 유지하며 모노톤 스택을 만드는 과정으로 응용할 수 있음. 오름차순이 확인되면 내림차순이 되기 전 while stack문을 계속 돌려 들어온 cow의 index로 pop되는 cow의 ans 변수를 update.

---

★ 25096 Pancake Deque ★

 

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

for i in range(1,int(input())+1):
    N=int(input())
    dq=deque(map(int,input().split()))
    ans=0
    cur=0
    for j in range(N):
        if j!=(N-1):
            x,y=dq.popleft(),dq.pop()
            if x<=y:#get x
                dq.append(y)
                if x>=cur:
                    cur=x
                    ans+=1
            else:#get y
                dq.appendleft(x)
                if y>=cur:
                    cur=y
                    ans+=1
        else:
            x=dq.pop()
            if x>=cur:
                ans+=1
    
    print(f'Case #{i}: {ans}')

 

🫶 일단 양쪽에서 꺼내고, 양쪽 중 deliciousness가 작은 것을 선택(greedy)해 서빙. 현재 cur보다 크거나 같으면 업데이트해서 ans 개수 += 1. 맨 마지막 1개 남았을 때는 무조건 꺼내서 해당 결과를 위와 동일하게 cur과 비교 

---

★ 2346 풍선 터뜨리기 ★

 

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

N=int(input())
balloons=list(map(int,input().split()))
ans=[]
dq=deque([(i,balloons[i-1]) for i in range(1,N+1)])
for _ in range(N):
    balloon = dq.popleft()
    ans.append(balloon[0])
    num=balloon[1]
    if len(dq)>=2:
        if num > 0: # +
            for _ in range(num-1):
                dq.append(dq.popleft())       
        else: #- (no 0)
            for _ in range(abs(num)):
                dq.appendleft(dq.pop())
print(*ans)

 

🫶 양수일 경우 오른쪽으로 돌고 / 음수일 경우 왼쪽으로 도는, 양방향으로 돌기에 deque 사용. 이 때 풍선을 터뜨리고 난 다음에는 자동으로 오른쪽으로 1칸 움직인 풍선이 deque의 맨 앞에 있으므로, 양수일 경우 num-1번 돌고 / 음수일 경우 abs(num)번 돌리는 구현 idea를 생각해야 함. 추가로 deque에 풍선이 1개 남았을 경우, 남은 풍선의 스텝 번호는 필요 없으므로 바로 종료.

---

★ 24511 queuestack ★

 

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

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
M=int(input())
C=list(map(int,input().split()))

ans=[]
dq=deque()
for a,b in zip(A,B):
    if a == 0:
        dq.append(b)

for c in C:
    dq.appendleft(c)
    ans.append(dq.pop())

print(*ans)

 

🫶 stack은 넣고 빼면 자기 자신이 넣고 빠지므로 영향  x / queue는 내가 들어가고 원래 들어가 있는 queue의 원소가 나옴. 즉, 여러 개의 queue만 연결된 거대한 deque 1개의 자료구조임을 알 수 있음. queue의 원소만 모아서 큰 1개의 deque으로 만들고, deque의 왼쪽에 넣으면서 오른쪽으로 1개씩 빼면 끝! 즉, stack 제외 queue만 일직선으로 모아서 1개의 deque으로 appendleft()와 pop() 연산

---

★ 12789 도키도키 간식드리미 ★

 

import sys
input=sys.stdin.readline

N=int(input())
s1=list(map(int,input().split()))
s1=s1[::-1]
order = 1
s2=[]

while s1:
    if order == s1[-1]:
        s1.pop()
        order+=1
        if order>N:
            print('Nice')
            sys.exit()
    else:
        while s2:
            if order == s2[-1]:
                s2.pop()
                order+=1
                if order>N:
                    print('Nice')
                    sys.exit()
            else:
                break
        s2.append(s1.pop())
if s2[::-1] == [x for x in range(order,N+1)]:
    print('Nice')
else:
    print('Sad')

 

🫶 두 개의 스택을 활용하는 문제. 일단 s1을 빼면서 order 맞다면 바로 빼고 order +=1 / order 틀리다면 s2를 돌리면서 order에 맞는 지 계속 확인 / s2까지 다 돌렸다면 s2에 s1.pop() 넣기 / 예외적으로 s1 모두 빼고 난 뒤 s2에 남은 일련번호가 줄 번호와 맞다면 Nice 출력 / 한 stack 내에 while 또 다른 stack 문 돌리기 기억

---

★ 15500 이상한 하노이 탑 ★

import sys
input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
B=[]
K=0
moves=[]
while N>0:
    if A and A[-1] == N:
        A.pop()
        K+=1
        moves.append((1,3))
        N-=1
        continue
    if B and B[-1] == N:
        B.pop()
        K+=1
        moves.append((2,3))
        N-=1
        continue
    if N in A:
        while A[-1] != N:
            B.append(A.pop())
            K+=1
            moves.append((1,2))
        A.pop()
        K+=1
        moves.append((1,3))
        N-=1
    else:
        while B[-1] != N:
            A.append(B.pop())
            K+=1
            moves.append((2,1))
        B.pop()
        K+=1
        moves.append((2,3))
        N-=1
print(K)
for x in moves:
    print(*x)

 

🫶 반드시 무게 순서대로 하노이 탑에 있어야 한다는 규칙이 없으므로, 그저 가장 무게가 많이 나가는 원판을 찾을 때까지 pop() + append() 반복하며 시뮬레이션으로 최종 막대에 넣어주면 된다.(이 때 list에 없는 경우만 주의 위해 A and A[-1] == N 이렇게 두 조건 and로 결합

---

★ 9523 Arithmetic with Morse ★

import sys
input=sys.stdin.readline

N=int(input())
morse = list(input().rstrip().split())
exp=[]
for code in morse:
    if code == '+' or code == '*':
        exp.append(code)
    else:
        mid = 0
        for x in code:
            if x == '=': mid+=10
            elif x == ':': mid+=2
            elif x == '.': mid+=1
            else: mid+=5
        exp.append(mid)
plus_stack=[]
ans=0
multiply = False
for x in exp:
    if x == '*':
        multiply = True
    elif x == '+':
        pass
    else:
        if multiply:
            plus_stack.append(plus_stack.pop() * x)
            multiply = False
        else:
            plus_stack.append(x)
print(sum(plus_stack))

 

🫶 일단 문제에 주어진 대로 +와 * 사이에 있는 각 모스 부호를 모두 숫자로 바꾸어 +와 * 사이의 숫자 add up

 

🫶 그러면 exp가 3 + 5 * 3과 같은 형태로 나온다. 이를 파이썬에서는 eval()로 한 방에 계산할 수 있으나, 스택을 활용해서도 간단하게 계산할 수 있다. 아래 그림 참고

: 스택에 +할 숫자들만 넣게 하기 위해 * 되는 숫자는 서로 숫자끼리 곱한 결과를 넣는다. 즉, A * B 형태가 있다면, * 기호를 만났을 경우 stack.pop()이 A이므로 * 기호를 만났다는 flag 변수 True 처리. 이후 flag 변수가 True일 때 앞선 stack.pop()과 곱한 결과를 다시 stack에 넣기. 이렇게 +와 *로 이루어진 식을 스택을 사용해 계산할 수 있다.

---