Baekjoon 1874번 스택 수열

문제

https://www.acmicpc.net/problem/1874

걸린 시간

00 : 37 : 38

풀이

Python3

class Stack():
    def __init__(self):
        self.stack = []

    def is_empty(self):
        return len(self.stack) == 0

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            return -1
        else:
            return self.stack.pop()

    def peek(self):
        return self.stack[-1]

if __name__ == "__main__":
    n = int(input())    

    # 스택 생성
    s = Stack()

    # 수열을 저장할 리스트
    sequence = []

    # 결과를 저장할 리스트
    result = []

    # 1부터 n까지 push 할 때 어디까지 저장되었는지 count 하는 변수
    count = 0

    # 수열을 이루는 정수를 입력받는다.    
    for i in range(0, n):
        sequence.append(int(input()))

    # 스택 자료구조를 이용해 수열을 만든다.
    for i in sequence:
        # 가져온 숫자까지 오름차순으로 push 한다.
        for j in range(count+1, i+1):
            s.push(j)
            result.append('+')
            count += 1

        # 만약 스택의 최상단에 있는 값이 수열과 일치하면
        if s.peek() == i:
            s.pop()
            result.append('-')
        else:    
            result.clear()
            result.append("NO")
            break

    for i in result:
        print(i)

수열은 수를 늘어놓고 순번을 붙이는 것이다. 규칙성은 있어도 되고 없어도 된다. 교육과정에서는 규칙적으로 나열된 수열만 다루기 때문에 예제의 불규칙한 수열을 보고 문제를 이해하는데 시간이 걸렸다.