(실버 II) 스택 시퀀스 – 1874

문제 링크

분류

데이터 구조, 스택

문제 설명

스택은 기본 데이터 구조 중 하나이며 컴퓨터 프로그램을 작성할 때 자주 사용되는 개념입니다.

스택은 데이터 입력(푸시) 및 데이터 추출(팝) 입구가 동일하므로 후입선출(LIFO) 특성을 갖습니다.

1에서 n까지의 숫자를 스택에 쌓았다가 꺼내서 일련의 숫자를 만들 수 있습니다.

이때 스택에 밀어넣는 순서는 반드시 오름차순이라고 가정하자. 임의의 시퀀스가 ​​주어지면 스택을 사용하여 시퀀스를 생성할 수 있는지 여부를 결정할 수 있으며, 그렇다면 어떤 순서로 푸시 및 팝 작업을 수행해야 하는지 결정할 수 있습니다.

계산하는 프로그램을 작성하세요.

입력

첫 번째 줄은 n(1 ≤ n ≤ 100,000)을 제공합니다.

두 번째 줄부터 n개의 줄에는 수열을 구성하는 1부터 n보다 작은 n까지의 정수가 순서대로 하나씩 주어진다.

물론 같은 정수는 두 번 나타나지 않습니다.

인쇄

입력 시퀀스를 만드는 데 필요한 작업을 한 줄에 하나씩 출력합니다.

푸시 작업은 +로 표시되고 팝 작업은 -로 표시됩니다.

불가능한 경우 NO를 출력한다.

import sys
input = sys.stdin.readline

N = int(input())

stack = ()
result = ()
start = 1
flag = True

for i in range(N):
    num = int(input())
    while start <= num:
        stack.append(start)
        result.append("+")
        start += 1

    if stack(-1) == num:
        stack.pop()
        result.append("-")
    else:
        flag = False
        break

if flag:
    for r in result:
        print(r)
else:
    print("NO")