Intro

스택을 만들어서 수를 저장하고, 그 스택에서 수를 뽑아내어 주어진 오름차순 수열을 만드는 문제이다. 못 만들면 "NO"를 출력한다.
처음에 문제를 이해하는데 시간이 정말 오래 걸렸다. 스택을 이용해 수열을 만든다는 게 무슨 뜻인지, push와 pop 연산을 언제 수행해야 하는지 한참 고민한 끝에 답을 찾았다.

Solution

문제에서 1부터 n까지의 수를 스택에 넣는다고 했다. 그러므로 반복문을 돌며 스택에 수를 1씩 추가한다.

또한 주어진 수열과 같은 수열을 만들어야 하므로, 주어진 수열의 0번째 수와 만들어놓은 스택의 마지막 수를 비교하며 연산을 선택한다.

이때 한 번이라도 주어진 수열의 0번째 수가 스택의 마지막 수보다 작다면, 수열을 만들 수 없다는 의미이므로 "NO"를 출력하고 종료한다.

Code

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

def main():
	n = int(input())
	seq = deque([int(input().strip()) for _ in range(n)])
	stack, answer = [0], []
	i = 1
	while seq:
		if stack[-1] == seq[0]:
			seq.popleft()
			stack.pop()
			answer.append("-")
		elif stack[-1] < seq[0]:
			stack.append(i)
			answer.append("+")
			i += 1
		elif stack[-1] > seq[0]:
			print("NO")
			return
	[print(a) for a in answer]

main()