BaekJoon 1874번 : 스택 수열 (python)

BaekJoon 1874번 : 스택 수열 (S2 38.102%)

스택의 성질을 이용하는 문제이기에 쉽게 풀 수 있었던 문제이다.

• 1부터 n까지 미리 저장해둔 temp에서 1부터 꺼내와서 stack에 넣기 시작한다.
• 만약 stack의 [-1]값과 지금 들어가야할 정답값과 동일하면 stack과 arr에서 둘다 pop을 해주고 result에 -기호를 append해준다.
• 만약 stack[-1]과 arr[-1]이 같지 않다면 stack에 temp값을 추가해주고 result에 +기호를 추가해준다.
• 그렇게 temp값이 다 빠져나왔다면 stack에 남아있는 모든 값들이 arr과 같아야 하기 때문에 stack과 arr에서 pop을 해준다.
• 만약 stack에 남아있는 값과 arr의 남아있는 값이 하나라도 같지 않다면 count flag를 통해 정답 출력 부분에서 예외처리를 해준다.

import sys
input = sys.stdin.readline

n = int(input())

arr = list()
temp = [i for i in range(1, n+1)]
for _ in range(n) :
    arr.append(int(input()))

temp = temp[::-1]
arr = arr[::-1]
stack = list()
result = ['+']
count = 0
stack.append(temp.pop())
while len(arr) != 0 :
    if len(temp) != 0 :
        if len(stack) == 0 :
            stack.append(temp.pop())
            result.append('+')
        if stack[-1] == arr[-1] :
            stack.pop()
            arr.pop()
            result.append('-')
        else :
            stack.append(temp.pop())
            result.append('+')
    else :
        if stack[-1] != arr[-1] :
            count = 1
        stack.pop()
        arr.pop()
        result.append('-')

if count == 1:
    print('NO')
else :
    for i in result :
        print(i)