💻 [백준][파이썬] 단계별로 풀어보기 - 스택, 큐, 덱(28278, 10773, 9012, 18258, 2164, 11866, 28279, 2346)

https://www.acmicpc.net/step/11

 

28278 스택2

import sys
input = sys.stdin.readline

N = int(input())

stack = []
result = []
for _ in range(N):
    command = input().split()

    # 1 X: 정수 X를 스택에 넣는다. 
    if command[0] == '1': 
        stack.append(int(command[1]))

    # 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
    elif command[0] == '2': 
        if stack:
            result.append(stack.pop())
        else:
            result.append(-1)

    # 3: 스택에 들어있는 정수의 개수를 출력한다.
    elif command[0] == '3': 
        result.append(len(stack))

    # 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
    elif command[0] == '4': 
        if stack: 
            result.append(0)
        else:
            result.append(1)
            
    # 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.
    elif command[0] == '5':
        if stack:
            result.append(stack[-1])
        else:
            result.append(-1)

print('\n'.join(map(str, result)))

 

10773 제로 

import sys
input = sys.stdin.readline

k = int(input())
stack = []

for _ in range(k):
    command = int(input())

    if command == 0:
        stack.pop()
    else:
        stack.append(command)
        
print(sum(stack))

 

9012 괄호 

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
    string = input().strip()
    stack = []
    is_vps = True

    for char in string:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if stack: # 스택에 ( 있으면 pop
                stack.pop()
            else: # 스택 비어있으면 VPS 아님 
                is_vps = False
                break

    # 스택이 비어있지 않으면 VPS 아님 
    if stack:
        is_vps = False

    print("YES" if is_vps else "NO")

• ')' 일 때 스택이 비어있으면 VPS 아님 
• 스택 연산 후, 스택 비어있지 않으면 VPS 아님 

18258 큐2 

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

N = int(input())
queue = deque()

for _ in range(N):
    command = input().split()

    # push X: 정수 X를 큐에 넣는 연산
    if command[0] == 'push':
        queue.append(int(command[1]))

    # 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력 
    # 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력
    elif command[0] == 'pop':
        if queue:
            print(queue[0])
            queue.popleft()
        else:
            print(-1)

    # size: 큐에 들어있는 정수의 개수를 출력
    elif command[0] == 'size':
        print(len(queue))

    # empty: 큐가 비어있으면 1, 아니면 0을 출력
    elif command[0] == 'empty':
        if queue:
            print(0)
        else:
            print(1)

    # front: 큐의 가장 앞에 있는 정수를 출력
    # 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력
    elif command[0] == 'front':
        if queue:
            print(queue[0])
        else:
            print(-1)

    # back: 큐의 가장 뒤에 있는 정수를 출력
    # 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력
    elif command[0] == 'back':
        if queue:
            print(queue[-1])
        else:
            print(-1)

• deque() 덱으로 구현하면 됨 ! 
• 나머지 연산들은 스택과 유사함 

2164 카드2

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

N = int(input())
queue = deque()

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

while len(queue) > 1:
    queue.popleft()
    queue.append(queue.popleft())

print(queue[0])

 

11866 요세푸스 문제0 

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

N, K = map(int, input().split())
queue = deque(range(1, N+1))
result = []

while queue:
    for _ in range(K-1):
        queue.append(queue.popleft())
    result.append(queue.popleft())

print("<" + ", ".join(map(str, result)) + ">")

• k번째 사람 제거:
  • 큐의 첫 번째 요소를 뒤로 옮기는 작업을 K-1번 반복 // K = 3이면 1, 2 뽑아서 맨 뒤로 보내고 
  • 그 후, K번째 사람을 제거하여 결과 리스트에 추가 // 3 뽑아서 결과리스트에 저장 

28279 덱2 

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

N = int(input())
queue = deque()

for _ in range(N):
    command = input().strip().split()

    if command[0] == '1': # 앞에 추가 
        queue.appendleft(int(command[1]))
    elif command[0] == '2': # 뒤에 추가 
        queue.append(int(command[1]))
    elif command[0] == '3':
        if queue: 
            print(queue.popleft())
        else:
            print(-1)
    elif command[0] == '4':
        if queue:
            print(queue.pop())
        else:
            print(-1)
    elif command[0] == '5':
        print(len(queue))
    elif command[0] == '6':
        if queue:
            print(0)
        else:
            print(1)
    elif command[0] == '7':
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif command[0] == '8':
        if queue:
            print(queue[-1])
        else:
            print(-1)

• 덱 앞에 추가 appendleft(), 뒤에 추가 append()
• 덱 앞에 삭제 popleft(),뒤에 삭제 pop()

 

💡 deque.rotate(n)

from collections import deque

queue = deque([1, 2, 3, 4, 5])

queue.rotate(2)  # 오른쪽으로 2칸
print(queue)  # [4, 5, 1, 2, 3]

queue.rotate(-3)  # 왼쪽으로 3칸
print(queue)  # [2, 3, 4, 5, 1]

• deque.rotate(n)은 큐를 오른쪽으로 n칸 회전시키는 함수입니다.
  • n>0: 오른쪽으로 n번 회전.
  • n<0: 왼쪽으로 |n|번 회전.
• rotate(+n)은 큐의 오른쪽 끝 요소를 앞으로 옮기는 것입니다.
• rotate(-n)은 큐의 왼쪽 끝 요소를 뒤로 옮기는 것입니다.

2346 풍선 터뜨리기 

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

N = int(input())
# 풍선 번호와 명령 저장 
queue = deque(enumerate(map(int, input().split()), start=1)) 
result = []

while queue: 
    index, step = queue.popleft() # 현재 풍선 번호와 명령어 가져오기 
    result.append(index) # 풍선 터뜨리기 

    if not queue:  # 남은 풍선이 없으면 종료 
        break
      
    # 큐를 step에 맞게 회전 
    if step > 0:
        queue.rotate(-(step-1)) # 오른쪽 이동 
    else:
        queue.rotate(-step)  # 왼쪽 이동 

print(" ".join(map(str, result)))

• 풍선과 명령이 짝을 이루므로 enmerate()로 함께 저장 ! 
• queue.rotate(-(step-1)) 
  • 이미 popleft()를 사용해 현재 위치를 1칸 앞으로 이동했으므로 추가로 오른쪽으로 step−1칸 이동.
  • rotate 함수는 양수를 오른쪽 회전으로 해석하므로, step−1칸 오른쪽 이동은 rotate(-(step - 1))로 표현 >> 이는 부호 반전 때문
    • rotate(+n) → 오른쪽 이동.
    • rotate(-n) → 왼쪽 이동이지만, 우리가 음수를 넣으면 이미 n 방향 반전이 된 회전을 실행하게 됩니다.