문제 출처 : https://www.acmicpc.net/problem/1874

난이도 : 실버 2

문제 파악

문제가 이해가 조금 어려웠다.

우리는 1부터 N까지의 숫자를 가지고 있다.

이 숫자들을 스택(stack) 에 넣었다가(push) 꺼내며(pop)
입력으로 주어진 목표 수열을 만들 수 있는지 확인해야 한다.

• push : 스택 맨 위에 숫자를 올린다
• pop : 스택 맨 위 숫자를 꺼낸다
• 중요한 제약 : push는 1 → 2 → 3 → … 순서대로만 할 수 있다
  (즉, “원하는 숫자만 골라 넣기”는 불가능)

만약 목표 수열을 만들 수 있다면,
우리가 했던 push/pop의 순서를 + / - 로 출력한다.

• push 할 때 +
• pop 할 때 -

만들 수 없다면 NO를 출력한다.

해결 아이디어 (직관)

목표 수열을 왼쪽부터 하나씩 처리한다고 하자.
지금 만들고 싶은 값이 x일 때:

1. 아직 push하지 않은 다음 숫자가 next라면,
   next <= x 인 동안 계속 push 해서 x가 스택 위에 올라오게 만든다. (+ 기록)

2. 이제 스택의 top이 x이면 pop 한다. (- 기록)

3. 그런데 top이 x가 아니라면?
   그 순간은 불가능하다.
   왜냐하면:

   • push는 오름차순이라 필요한 숫자를 “건너뛰어” 넣을 수 없고
   • pop은 top에서만 되어서 “밑에 있는 숫자”를 바로 꺼낼 방법이 없다

   -> NO를 출력해줘야 한다.

예제 1 흐름

목표: 4 3 6 8 7 5 2 1
초기 상태: 스택 [], next=1

(1) 목표 4 만들기

• 1 push + → [1]
• 2 push + → [1,2]
• 3 push + → [1,2,3]
• 4 push + → [1,2,3,4]

4에서 pop 을 해준다.

• top=4 pop - → [1,2,3]

(2) 목표 3 만들기

• top=3 pop - → [1,2]

(3) 목표 6 만들기

• 5 push + → [1,2,5]
• 6 push + → [1,2,5,6]
• top=6 pop - → [1,2,5]

(4) 목표 8 만들기

• 7 push + → [1,2,5,7]
• 8 push + → [1,2,5,7,8]
• top=8 pop - → [1,2,5,7]

(5) 목표 7 만들기

• top=7 pop - → [1,2,5]

(6) 목표 5 만들기

• top=5 pop - → [1,2]

(7) 목표 2 만들기

• top=2 pop - → [1]

(8) 목표 1 만들기

• top=1 pop - → []

이렇게 끝까지 가능하면, 우리가 기록한 +/- 를 그대로 출력하면 된다.

---

“NO”가 되는 흐름 (불가능한 경우)

목표 수열이 3 1 2 라고 해보자 (N=3)

초기: 스택 [], next=1

목표 3 만들기

• 1 push + → [1]
• 2 push + → [1,2]
• 3 push + → [1,2,3]
• pop - → [1,2]

목표 1 만들기

근데 지금 스택 top은 2다.
스택은 top에서만 pop 할 수 있으니 1을 꺼내려면 2를 먼저 꺼내야 한다.

하지만 목표는 “지금 당장 1”이라서
2를 먼저 꺼내는 순간 목표 수열이 깨진다.

→ 그래서 이 경우는 불가능, NO

---

해답 및 풀이

import sys
input = sys.stdin.readline

n = int(input().strip())

targets = []  
for _ in range(n):
    targets.append(int(input()))


# targets = [4, 3, 6, 8, 7, 5, 2, 1]

stack = []
ops = []

cur_num = 1

for x in targets:
    # x가 스택에 올라올 때 까지 push 한다.
    while cur_num <= x:
        stack.append(cur_num)
        ops.append("+")
        cur_num += 1
    
    # 이제 스택 top이 x면 pop 해준다.
    if stack and stack[-1] == x:
        stack.pop()
        ops.append("-")
    
    # 스택에 올라올 때 까지 push했는데도, 스택에 top이 x가 아니라는 것은 x를 꺼낼 바업이 없다.
    else:
        print("NO")
        sys.exit(0)

print("\n".join(ops))