[python] 백준 1874번 오답노트

지금까지 만난 자료구조 문제중에 제일 어려웠다 ㅠㅠ

import sys
input = sys.stdin.readline
n = int(input())
stack = []

nlst = []
for i in range(n):
    new = int(input())
    nlst.append(new)

cnt = 1
ans = []
tes = 1

for i in nlst:
    while cnt <= i:
        ans.append('+')
        stack.append(cnt)
        cnt+=1
    if stack[-1] >i:
        tes = 0
    if stack[-1] == i:
        ans.append('-')
        stack.pop()
if tes == 1:
    for i in ans:
        print(i)
else:
    print('NO')

구문풀이

nlst = []
for i in range(n):
    new = int(input())
    nlst.append(new)

n개의 입력을 list에 추가한다.

cnt = 1
ans = []
tes = 1

cnt는 stack에 넣은 숫자이고 ans는 +와-를 저장할 곳이고 tes는 출력 여부를 테스트하는 곳이다.

for i in nlst:
    while cnt <= i:
        ans.append('+')
        stack.append(cnt)
        cnt+=1
    if stack[-1] >i:
        tes = 0
    if stack[-1] == i:
        ans.append('-')
        stack.pop()

n을 하나씩 꺼낸다.
cnt=1 에서 n보다 cnt가 같게될 때 까지 +를 ans에 더한다.
그리고 스택에는 cnt=1,2,..n까지를 추가한다.

stack 마지막 원소가 n보다 커지면 tes에 0을 담는다. ('NO')가 되어야 하기 때문

stack 마지막 원소가 n이면 -를 ans에 추가하고 stack에서 꺼낸다.

if tes == 1:
    for i in ans:
        print(i)
else:
    print('NO')

NO를 출력할지 출력을 할 수 있을지 결정한다.