✅ 문제 풀이
🎈 9012 괄호
입력 데이터 개수를 나타내는 T가 주어지고, t줄 만큼의 괄호가 주어질때 완성된 괄호를 보이는 괄호 문자열을 VPS라 할 때, 주어진 문자열이 VPS이면 Yes를, 아니면 No를 하나씩 출력한다.
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
vps = input()
stack = []
for i in vps:
if i == '(':
stack.append(i)
elif i == ')':
if stack:
stack.pop()
else:
print('NO')
break
else:
if stack:
print('NO')
else:
print('YES')< 풀이 과정 >
for문으로 t회 동안 반복하여 vps를 입력받고, vps 내 문자인 괄호가 ( 형태면, stack에 집어넣고 )인 경우 stack이 있으면 pop, 없으면 NO를 출력하고 break 한다.
이후 else로 stack에 값이 남아있다면 (가 있는 것으로 올바른 괄호가 아닌 것을 의미하므로 NO를 출력하고, 아니면 YES를 출력한다.
🎈 10828 스택
명령의 수 N개를 입력받고 N줄 동안 다음과 같은 명령어가 주어진다.
- PUSH X : 정수 X를 스택에 넣는다
- POP : 스택에서 가장 위에 있는 정수 빼고, 없다면 -1 출력
- size : 스택에 들어있는 정수 개수 출력
- empty : 스택이 비어있으면 1, 아님 0을 출력
- top : 스택의 가장 위에 정수 출력, 스택에 정수가 없는 경우 -1 출력
import sys
input = sys.stdin.readline
n = int(input())
stack = []
for i in range(n):
command = input().split()
if command[0] == 'push':
stack.append(command[1])
elif command[0] == 'pop':
if not stack:
print(-1)
else:
print(stack.pop())
elif command[0] == 'size':
print(len(stack))
elif command[0] == 'empty':
if not stack:
print(1)
else:
print(0)
elif command[0] == 'top':
if not stack:
print(-1)
else:
print(stack[-1])< 풀이 과정 >
LIFO 구조인 스택에 따라서 주어진 push, pop, size, empty, top 명령어를 for문으로 n번 돌면서 입력받는 command에 따라 구현하는 문제
🎈 10845 큐
정수 n을 입력받아 n줄 만큼 다음의 명령을 입력받는다.
- push x : 정수 x를 큐에 넣는다.
- pop : 큐에서 가장 앞에 정수 빼고 출력, 큐가 비어있으면 -1 출력
- size : 큐에 들어있는 정수 개수 출력
- empty : 큐가 비었으면 1, 아니면 0 출력
- front : 큐의 가장 앞에 정수 출력, 큐가 비었으면 -1을 출력
- back : 큐의 가장 뒤에 있는 정수 출력, 큐가 비었으면 -1을 출력
import sys
n = int(sys.stdin.readline())
queue = []
for i in range(n):
command = sys.stdin.readline().split()
if command[0] == 'push':
queue.append(command[1])
elif command[0] == 'pop':
if queue:
print(queue.pop(0))
else:
print(-1)
elif command[0] == 'size':
print(len(queue))
elif command[0] == 'empty':
if queue:
print(0)
else:
print(1)
elif command[0] == 'front':
if queue:
print(queue[0])
else:
print(-1)
elif command[0] == 'back':
if queue:
print(queue[-1])
else:
print(-1)< 풀이 과정 >
FIFO 구조로 이루어진 Queue를 n개의 명령어를 for문으로 n번 돌며 입력받는 command에 따라 구현하는 문제
🎈 2164 카드 2
n장의 카드가 주어지고 차례대로 n까지의 번호가 부어있고 1번카드가 제일 위에, n번 카드가 제일 아래에 순서대로 카드가 놓여있다. 주어진 카드가 있을 때, 카드를 버리고 제일 위에 놓인 카드를 제일 아래 칸으로 옮기는 작업을 반복할 때 제일 마지막에 남게 되는 카드의 번호를 구하는 프로그램을 출력하시오
from collections import deque
import sys
input = sys.stdin.readline
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.pop())< 풀이 과정 >
일반 queue를 만들어 pop(0)을 이용하면 시간초과가 뜨는 문제
확실히 deque 모듈을 활용하면 CPython으로 구성되어있어 속도면에서 확실히 차이를 보이는 듯하다.
일반적인 queue.queue를 사용하면 멀티스레딩으로 인한 큐로 되어 있어 더 오래걸리는 문제를 보인다.
🎈 1874 스택 수열
n과 n개의 줄에는 수열을 이루는 정수가 주어질 때, 반드시 순서는 오름차순을 지키도록 할 때, push연산이 필요하면 +, pop연산은 -, 불가능한 경우 NO를 출력하는 문제
import sys
input = sys.stdin.readline
n = int(input())
idx = 1
flag = True
stack = []
operation = []
for _ in range(n):
num = int(input())
while idx <= num:
stack.append(cnt)
idx += 1
operation.append('+')
if stack[-1] == num:
stack.pop()
operation.append('-')
else:
flag = False
if not flag:
print('NO')
else:
for i in operation:
print(i)< 풀이 과정 >
1~n까지의 수가 스택에 있고, 스택 끝 값이 input으로 주어지면 pop하는 방식으로 구현하였다.
+, - 표시를 나타내주기 위해 operation 리스트를 만들었고, 오름차순 순서 나열을 비교하기 위해 idx로 값을 나열한 뒤 num보다 작다면 append 즉 push연산을 진행하고, 끝 값이 입력받는 정수 num과 일치하면 pop연산을 진행한다.
불가능한 케이스를 확인하기 위해 flag = False로 지정하여 NO를 출력하도록 하였다.
🎈 1966 프린터 큐
테스트케이스 수 t가 주어지고, 문서 N개와 몇번째로 인쇄되는지 확인해야하는 문서 순서가 주어진다. 프린터 기기에 문서의 중요도가 주어지고, queue에서 원하는 문서가 몇번째로 인쇄되는지 출력하는 문제
import sys
from collections import deque
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
queue = deque(list(map(int, input().split())))
importance = 0
while queue:
maxi = max(queue)
front = queue.popleft()
m -= 1
if maxi != front:
queue.append(front)
if m < 0:
m = len(queue) - 1
else:
importance += 1
if m < 0:
print(importance)
break
< 풀이 과정 >
deque로 queue를 입력받은 후, queue에서 m번째 문서가 몇번째로 인쇄되는지 구분하기 위해 importance 변수를 만들어 준다.
현재 위치한 queue 중 가장 큰 값을 maxi로 저장한 후 popleft할때마다 m을 1씩 감소시킨다.
만일 queue내 최댓값이 front와 일치하지 않는데 m이 음수가 된다면 m은 queue의 가장 뒤 인덱스 값으로 변환하고, 일치하면 importance를 + 1씩 더해주고 m이 음수가 되면 importance 값을 출력하고 종료한다.
