[BaekJoon 1874 : Data Structure, Python] - 스택 수열

백준 1874 스택 수열 : 실버 2

Solution

import sys 

n = int(input())
data = list(map(lambda x: int(x.rstrip()), sys.stdin.readlines()))

def makeSeq(n):
    myStack = []
    result = []
    num = 1  

    for i in range(n):
        cur = data[i]

        while len(myStack) == 0 or myStack[-1] < cur:   
            myStack.append(num)
            result.append("+")
            num += 1

        if myStack[-1] > cur:   
            return "NO"

        elif myStack[-1] == cur:
            myStack.pop()
            result.append("-")

    return '\n'.join(result)

print (makeSeq(n))

풀이과정 및 느낀점

주어진 수열을 스택 자료구조를 통해 구현하기 위해 어떤 순서로 계산해야 하는지 +(push), -(pop) 형태로 출력해야 하는 문제이다. 스택에 들어가는 순서가 반드시 오름차순이고, 스택의 LIFO 특성 역시 고려해야 하기 때문에 push, pop 조건을 코드로 구현하는 과정이 까다로웠다.

우선, stack 의 마지막 숫자가 현재 목표하는 숫자보다 큰 경우, 주어진 조건을 만족하며 수열을 구현할 수 없기 때문에 “No” 를 return 한다.
stack 이 비어있거나, top 숫자가 cur 보다 작은 경우, 같아질 때까지 num 을 하나씩 올려가며 추가해주고, push 기호인 “+” 를 result 리스트에 append 시켜준다.
같은 경우에는 그 숫자가 수열에 포함될 수 있도록 pop 시켜주고 “-“ 기호를 result 에 append 한다.