BOJ 1874 - 스택 수열

folder_open Algorithm / BOJ / silver | date_range last modified at / created at 09 Oct 2024

sell #BOJ #1874 #silver #python #파이썬 #코딩테스트 #알고리즘

맨 위로

• 문제 링크
• 잡담
• 구현 과정
• 코드

문제 링크

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

잡담

4달 전에 (24.05.23) 제출했던 기록이 있다. 지금 보니 answer문자열을 += 이런 식으로 한다던지 시간적으로 비효율적인 짓을 많이한 것 같다. 그래도 지금 코드가 더 나아진 것 같아서 기분은 좋다.

구현 과정

문제 자체가 어렵진 않다. 어차피 스택이라 중간값은 볼 수가 없으니, pop해야할 숫자를 기억하다가 push했을 때부터 쭉 pop해주고, 이런 식으로 반복하면 된다고 생각했다.

코드

from sys import stdin
input = stdin.readline


n = int(input())
seq = []
for _ in range(n):
    seq.append(int(input()))
stack = []
topop = 0
answer = []
try:
    for i in range(1, n + 1):
        stack.append(i)
        answer.append('+')
        while stack and stack[-1] == seq[topop]:
            stack.pop()
            answer.append('-')
            topop += 1
except IndexError:
    print("NO")
if stack:
    print("NO")
else:
    for i in answer:
        print(i)