백준 1874 스택 수열

문제

스택 수열

스택에 값을 push, pop하며 그에 대응하는 +, -를 출력하자

난이도 : Silver2

---

풀이

1. 스택을 이용한 문제 풀이 (상세 아래 코드 참조)

---

코드

import sys

n = int(sys.stdin.readline())
data = [int(sys.stdin.readline()) for _ in range(n)]


def solution(data: list):
    answers = []
    stack = [0]
    max_last = 0  # 최대 값 저장
    
    for d in data:
        stack_last = stack.pop() if stack else d  # stack이 비어 있으면 인풋 값을 사용
        if stack_last > d:  # 인풋 값보다 stack 마지막 값이 더 크면 pop
            if stack[-1] != d:  # stack의 마지막 값과 인풋 값(pop 값)이 다르면, 조건을 충족하지 못하므로 False
                return []
            answers.append('-')
            
        else:           
            for i in range(max_last, d):  # 현재 인풋과 최대값 차이만큼 + 추가
                stack.append(i+1)
                answers.append('+')
            answers.append('-')
            max_last = d if max_last < d else max_last  # ex) 4 3 6 순서라면, 3이 아닌 4와의 차이만큼 +를 추가해야 함
    return answers

answers = solution(data)
if answers:
    for i in answers:
        print(i)
else:
    print('NO')