[백준/Python] 1874. 스택 수열

 📌문제 유형: 스택

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

 

 

---

📌 풀이 

 

처음에 문제를 이해하지 못해서 꽤나 헤맸었다.. (입력된 수열로 오름차순을 만들라는 줄 알고)

 

찬찬히 문제를 읽어보면, 

 

1. 1~n의 수를 이용한다. 

2. push는 오름차순으로 진행한다. 

3. 입력된 수열이 스택에서 push/pop한 결과물이어야 한다. 

 

따라서 1부터 n까지 직접 적어보며 push와 pop을 언제하게 되는지 해보면 된다. 

 

1번 예제로 설명해보면, 입력이 8 4 3 6 8 7 5 2 1 이다. 

N = 8이고 결과 수열 = 4 3 6 8 7 5 2 1
add = 1로 카운트해보자. 

add = 1 ~ 4까지 push 
pop
pop ==> 4 3 완료 / stk = 1 2
add = 5, 6 push 
pop ==> 4 3 6 완료 / stk = 1 2 5
add = 7, 8 push (add == N이므로 push stop) 
pop 
pop
pop
pop
pop ==> 4 3 6 8 7 5 2 1 완료 

 

이때 push 할 때는 '+'를, pop할 때는 '-'를 출력하면 된다. 

 

이를 코드로 구현하게 되면 아래와 같다. 

 

n = int(input())
stack = []
ops = []
add = 1
able = True
for i in range(n):
    x = int(input())
    while add <= x:
        stack.append(add)
        ops.append('+')
        add += 1
    if stack[-1] == x:
        stack.pop()
        ops.append('-')
    else:
        able = False
        break
if able:
    for i in ops:
        print(i)
else:
    print("NO")