[백준][Python 파이썬] 1874번 스택 수열

 

상태 변화를 체크할 변수들을 몇 개 선언하고, 실제로 스택에 수를 넣었다가 빼는 작업을 하면 되는 문제다. 

 

1. queue 변수에는 스택에서 출력해야 하는 변수들을 차례대로 입력받아 넣었다. 

2. stack 변수는 실제 스택 역할을 하는 변수이다. 

3. maxNum 변수는 스택에 들어갔었던 가장 큰 숫자 값을 저장하는 변수이다. 스택에 push를 할 때는 모든 원소를 오름차순으로 넣어야 하기 때문에 이 값이 필요했다.

4. ops 변수는 스택에서 어떤 연산이 수행되었는지 그 값들을 모으기 위한 리스트 변수이다. 

 

queue 변수는 데크 자료형으로 선언해서, 맨 앞에서 원소를 뺄 때도 O(1) 시간에 제거할 수 있도록 했다. 

 

만약 현재 stack에서 출력되어야 하는 원소(queue의 맨 앞에서 빼낸 원소)가 stack의 maxNum 값보다 크다면, stack에 수를 더 넣어야 한다는 뜻이므로 for문을 사용해서 stack에 원소를 1씩 증가시키며 추가해 주었다. 또한 stack에 원소를 추가할 때마다 ops 변수에도 "+" 값을 추가해 주었다. 

 

만약 그렇지 않다면, queue에서 빼낸 원소와 stack의 맨 뒤의 값이 일치하는지를 확인했다. 두 값이 일치한다면 해당 값을 stack에서 빼내서 출력해야 하므로 stack에서 pop()으로 원소를 빼내고, ops 변수에도 "-" 값을 추가해 주었다. 

 

또한 queue와 stack에는 모두 1부터 N까지의 원소가 들어갔다 나와야 하기 때문에, 정상적으로 수행되었다면 queue가 빌 때 stack도 비어야 한다. 

만일 그렇지 않다면 중간에 queue에서 빼낸 값과 stack의 맨 뒤의 값이 일치하지 않아서 stack에서 원소를 빼낼 수 없었다는 뜻이므로, while 문을 다 돌려보면 queue는 비는데 stack에는 원소가 남게 된다. 

 

따라서 이 경우에만 에러를 출력한다. 

 

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

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

for _ in range(N):
    queue.append(int(input()))
    
stack = []
ops = []
maxNum = 0

while queue:
    
    elem = queue.popleft()
    
    if maxNum < elem:
        for i in range(maxNum+1, elem+1):
            stack.append(i)
            ops.append("+")
        maxNum = max(max(stack), maxNum)
    
    if stack and elem == stack[-1]:
        stack.pop()
        ops.append("-")
        
if stack:
    print("NO")
else:
    for op in ops:
        print(op)