백준_단계별로 풀어보기_16단계_스택, 큐, 덱

스택, 큐, 덱 단계 (acmicpc.net)

스택, 큐, 덱 자료구조를 사용하여 문제를 해결해 봅시다.

스택, 큐, 덱 단계

---

■ 백준 28278 스택 2_실버 4

- 스택의 개념을 익히고 실습하는 문제

# import sys
# stk = []
# for _ in range(int(input())):
#     m = list(map(int, sys.stdin.readline().split()))
#     if len(m) == 1:
#         if m[0] == 2:
#             print(stk.pop() if stk != [] else -1)
#         elif m[0] == 3:
#             print(len(stk))
#         elif m[0] == 4:
#             print(1 if stk == [] else 0)
#         elif m[0] == 5:
#             print(stk[-1] if stk != [] else -1)
#     else:
#         stk.append(m[1])

#고수코드: 슬라이싱으로 두 자리 수 이상 입력 / 답변list 만들어서 한번에 출력
import sys
input = sys.stdin.readline
def solution():
    N = int(input())
    stack = []
    res = []
    for _ in range(N):
        cmd = input().rstrip()
        if cmd[0] == '1':
            stack.append(cmd[2:])
        elif cmd[0] == '2':
            res.append(stack and stack.pop() or '-1')
        elif cmd[0] == '3':
            res.append(f'{len(stack)}')
        elif cmd[0] == '4':
            res.append(f'{(not stack)*1}')
        else:
            res.append(stack and stack[-1] or '-1')
    print('\n'.join(res))
solution()

 

■  백준 10773 제로_실버 4

- 가장 최근에 쓴 수를 지우는 문제

import sys
stk = []
for _ in range(int(input())):
    n = int(sys.stdin.readline())
    if n == 0: stk.pop()
    else: stk.append(n)
print(sum(stk))

 

■ 백준 10773 괄호_실버 4

- 주어진 문자열이 올바른 괄호열인지 판단하는 문제

# import sys
# for _ in range(int(input())):
#     ps = sys.stdin.readline().rstrip()
#     stk = []
#     for x in ps:
#         if stk==[]: stk.append(x)
#         elif stk[-1]=="(" and x==")":
#             stk.pop()
#         else: stk.append(x)
#     print("YES" if stk==[] else "NO")

#고수코드: replace 메서드로 최소 vps(쌍 괄호)를 공란으로 치환 반복
import sys
vps = sys.stdin.readlines()[1:]
for v in vps:
    v = v.rstrip()
    while '()' in v:
        v = v.replace('()', '')
    if v: print('NO')
    else: print('YES')

 

■ 백준 4949 균형 잡힌 세상_실버 4

- 위와 같은데 괄호의 종류가 다양해진 문제

# import sys
# while True:
#     s = sys.stdin.readline().rstrip()
#     stk = []
#     if s==".":
#         break
#     else:
#         for x in s:
#             if x in "()[]":
#                 if stk==[] or x in "([":
#                     stk.append(x)
#                 elif stk[-1]=="(":
#                     if x==")": stk.pop()
#                     elif x=="]": break
#                 elif stk[-1]=="[":
#                     if x == "]": stk.pop()
#                     elif x == ")": break
#     print("no" if stk else "yes")

#고수코드:()[]쌍의 개수가 맞지 않으면 no를 출력하고 replace 메서드로 간편하게 구현
import sys
while True:
    s = sys.stdin.readline().rstrip()
    if s==".":break
    if s.count("(")!=s.count(")") or s.count("[")!=s.count("]"):print("no");continue
    b=""
    for i in s:
        if i in "()[]":
            b+=i
    while "()" in b or "[]" in b:
        if "()" in b:b=b.replace("()","")
        if "[]" in b:b=b.replace("[]","")
    if b=="":print("yes")
    else:print("no")

 

■ 백준 12789 도키도키 간식드리미_실버 3

- 스택을 활용하여 오름차순으로 학생을 빼내는 문제

n = int(input())
li = list(map(int, input().split()))
ans = []
stk = []
for i in range(1, n+1):
    if i in li:
        while li[0] != i:
            stk.append(li.pop(0))
        ans.append(li.pop(0))
    else:
        ans.append(stk.pop())
print("Nice" if ans == sorted(ans) else "Sad")

 

■ 백준 18258 큐 2_실버 4

- 큐의 개념을 익히고 실습하는 문제

• pop()의 시간복잡도는 O(1)인 반면 pop(0)의 시간복잡도는 O(N)이기 때문에 시간이 오래 걸린다.
• 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

import sys
from collections import deque
dq = deque()
res = []
li = sys.stdin.readlines()[1:]
for x in li:
    command = x.split()[0]
    if command == "push":
        dq.append(x.split()[1])
    elif command == "pop":
        res.append(dq.popleft() if dq else '-1')
    elif command == "size":
        res.append(str(len(dq)))
    elif command == "empty":
        res.append('0' if dq else '1')
    elif command == "front":
        res.append(dq[0] if dq else '-1')
    elif command == "back":
        res.append(dq[-1] if dq else '-1')
sys.stdout.write("\n".join(res))

 

■ 백준 2164 카드2_실버 4

- 큐를 사용하여 동작을 구현하는 문제

from collections import deque
dq = deque(range(1, int(input())+1))

while len(dq) != 1:
    dq.popleft()
    if len(dq) == 1: break
    dq.append(dq.popleft())
print(*dq)

 

■ 백준 11866 요세푸스 문제 0_실버 5

- 큐를 활용하여 배열을 돌리는 문제 (참고 https://wakaranaiyo.tistory.com/248)

from collections import deque
n, k = map(int, input().split())
q = deque(range(1, n+1))
ans = []
while q:
    for _ in range(k-1):
        q.append(q.popleft())
    ans.append(str(q.popleft()))
print(f"<{', '.join(ans)}>")

# #고수코드:
# N, K = map(int, input().split())
# circle = [i for i in range(1, N+1)]
# ans = []
# idx = 0
#
# for _ in range(N):
#     idx += K-1
#     if(idx >= len(circle)):
#         idx %= len(circle)
#     ans.append(str(circle.pop(idx)))
# print('<', ', '.join(ans), '>', sep='')

 

■ 백준 28279 덱 2_실버 4

- 덱의 개념을 익히고 실습하는 문제

- 참고: collections — Container datatypes — Python 3.12.0 documentation

import sys
from collections import deque
li = sys.stdin.readlines()[1:]
dq = deque()
ans = []
for x in li:
    commander = x.split()[0]
    if commander == "1":
        dq.appendleft(x.split()[1])
    elif commander == "2":
        dq.append(x.split()[1])
    elif commander == "3":
        ans.append(dq.popleft() if dq else "-1")
    elif commander == "4":
        ans.append(dq.pop() if dq else "-1")
    elif commander == "5":
        ans.append(str(len(dq)))
    elif commander == "6":
        ans.append("0" if dq else "1")
    elif commander == "7":
        ans.append(dq[0] if dq else "-1")
    elif commander == "8":
        ans.append(dq[-1] if dq else "-1")
sys.stdout.write("\n".join(ans))

 

■ 백준 2346 풍선 터뜨리기_실버 3 (복습)

- 덱을 활용하여 배열을 양방향으로 돌리는 문제

• deque의 rotate 기능을 활용하여 쉽게 원형큐를 양방향으로 관리할 수 있다.

from collections import deque
ans = []
input()
li = list(map(int, input().split()))
dq = deque((val, idx+1) for idx, val in enumerate(li))
while dq:
    v, i = dq.popleft()
    ans.append(str(i))
    if v > 0: dq.rotate(1-v)
    else: dq.rotate(-1*v)
print(" ".join(ans))

 

■ 백준 24511 queuestack_실버 3 (복습)

- 큐와 스택의 이해를 시험하는 문제

• 시간복잡도를 일찌감치 파악하고 결론 도출 (참고: https://www.acmicpc.net/board/view/84357)

import sys
n = int(sys.stdin.readline())
st = sys.stdin.readline().split()
qs = sys.stdin.readline().split()
m = int(sys.stdin.readline())
x_arr = sys.stdin.readline().split()
ans = []
q = [qs[i] for i in range(n) if st[i] == "0"]
q.reverse()
print(" ".join((q+x_arr)[:m]))