Problem Solving/Online Judge
[BOJ] #1874 - 스택 수열
se0m
2021. 6. 12. 02:01
1874번: 스택 수열
1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.
www.acmicpc.net
** 문제 유형
- 스택, 그리디
** 풀이
- 스택에 원소 삽입시, 단순히 특정 수에 도달할 때까지 삽입
- 스택에서 원소를 연달아 빼낼 경우, 그 수들이 내림차순으로 빠지는지 확인
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))