[Stack] 1874 스택 수열

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

import sys
input = sys.stdin.readline

n = int(input())
find = []
for i in range(n):
    find.append(int(input()))

stack = [] # 임의의 스택
number = [i for i in range(1, n+1)] # 1~n까지의 수 => 스택에 넣었다 뺴면서 원하는 수열을 완성할 수 있는지 check
answer=[]
plusminus=[]
index=0
while number:
    stack.append(number.pop(0)) # 일단 스택에 넣음 -> +
    plusminus.append("+")
    while stack and stack[-1]==find[index]:
        index+=1
        answer.append(stack.pop()) # 스택의 제일 위의 값이 찾는 값과 일치 -> -
        plusminus.append("-")


while stack:
    answer.append(stack.pop()) # 스택에서 뻄 -> +
    plusminus.append("-")

if find == answer:
    for i in plusminus:
        print(i)
else:
    print("NO")

일단 스택에 1~n의 값을 집어넣고 스택의 가장 위의 값과 찾는 값을 비교

-> 찾는 값과 일치하면 스택에서 빼고, answer에 append

-> 찾는 값과 일치하지 않으면 그 다음 값을 스택에 넣음

 

마지막에 스택에 값이 남아있다면 모두 answer에 LIFO형태로 넣어줌

 

find와 answer가 같다면? push, pop연산을 저장한 값들을 출력

같지 않다면? 스택을 만들 수 없다는 뜻이므로 "NO"출력

 

---

 

[ref] 유사한 문제 - 주차 관리인

https://bokoo.tistory.com/11

[Stack] 주차 관리인