[BOJ] #1874 - 스택 수열

1874번: 스택 수열

 

** 문제 유형

• 스택, 그리디

 

** 풀이

1. 스택에 원소 삽입시, 단순히 특정 수에 도달할 때까지 삽입
2. 스택에서 원소를 연달아 빼낼 경우, 그 수들이 내림차순으로 빠지는지 확인

 

n = int(input())

cur = 1
stack = []
rslt = []

for i in range(1, n + 1):
    out = int(input())

    while cur <= out: # 입력된 수에 도달할 때까지 삽입
        stack.append(cur)
        rslt.append('+')
        cur += 1

    if stack[-1] == out: # 스택의 최상위 원소일 때
        stack.pop()
        rslt.append('-')
    else: # 불가능한 경우
        print("NO")
        exit(0)

print('\n'.join(rslt))