[백준] 1874 스택수열 (Python)

오랜만에 다시 시도한 스택수열. 약간의 막힘이 있어 검색을 통해 일부 힌트를 얻었다. 그리고 문제를 제대로 읽지 않은 나의 착오로 헛시간을 좀 낭비했다.

스택은 LIFO의 구조로 나중에 들어온 데이터가 가장 먼저 나가는 구조이다. 즉, 간단히 보면 스택수열은 오름차순인 리스트를 내림차순으로 바꾸는 것과 동일하다. 물론, 핵심 동작 자체는 그렇다. 중요한 것은 중간에 숫자가 추가 된다는 것이다. 
예제를 보면 1~4까지 오름차순 리스트를 먼저 만들고, 4와 3을 뺐다가 중간에 5~8을 넣고 빼고 하는 과정이 있다. 이 부분 때문에 정말 고민했다. 중간부터 들어오는 수열을 따로 관리하는 방법을 몰라서 계속 고민하다가 검색을 통해 힌트를 얻은 것이 시작점을 변수에 저장하는 방법이었다.

import sys

# 1874 스택수열
T = int(input())
answer = []
asc_list = []
PUSH, POP = "+", "-"
start = 0

for i in range(T):
    N = int(sys.stdin.readline())
    
    if N > start:
        for i in range(start+1, N+1):
            asc_list.append(i)
            answer.append(PUSH)
        start = N
    elif asc_list[-1] != N:
        print("NO")
        sys.exit()
    print(asc_list)

    asc_list.pop()
    answer.append(POP)

for i in range(len(answer)):
    print(answer[i])

start라는 변수를 새로 만들어주고 해당 변수보다 1이 큰 숫자부터 입력된 숫자까지 넣어준다면 중간에 추가되는 수열을 이상없이 관리할 수 있게 된다. 이게 이 문제의 핵심이지 않았을까 싶다.

그리고 스택의 특성상 오름차순 리스트의 마지막 데이터보다 작은 수를 먼저 뽑고자 하면 수열이 만들어질 수 없기 때문에 이를 NO로 출력하게끔 했다. 문제에서도 수열이 만들어질 수 없을 경우에는 NO로 출력하라고 주어졌다.

웃긴건 마지막에 print문을 이상하게 출력하는 것을 알아채지 못해서 답이 왜 틀렸는지 3~4번은 더 봤다는 것이다.
(바보같이 print(answer) 해놓고 제출하니까 틀리지.. 어휴!)