[BOJ] 파이썬 - 1874 스택 수열

문제 링크 : https://www.acmicpc.net/problem/1874

파이썬 코드

import sys

n=int(sys.stdin.readline())

stack=[] 
result=[]
check=0
i=1

for _ in range(n):
    num=n=int(sys.stdin.readline())
    while i<=num:
        stack.append(i)
        result.append('+')
        i+=1
    if stack[-1]==num:
        stack.pop()
        result.append('-')
    else:
        check=1
        print('NO')
        break

if check==0:
    for j in result:
        print(j) 

처음엔 문제가 이해되지 않아서 헤맸다.. 문제 페이지에 있는 힌트를 참고하면 좋다.

1,2,3,4... n 을 차례대로 스택에 push한 후, 스택의 top이
입력한 num과 같다면 pop 해주면 된다.

문제 예제는 4,3,6,8 .. 순으로 num을 입력한다.

num이 될 때까지의 숫자를 스택에 push한다.
처음엔 1,2,3,4가 스택에 push 되고, 이 때 top은 4가 된다.
4를 pop해주면
다음 top은 3이 된다.
입력 순서가 4,3이니까 3도 pop 해준다.
이제 top은 2인데, 3 다음 입력 num은 6이다.
따라서 스택의 top이 6이 될 때까지 또 숫자를 스택에 push해준다.

while문을 빠져나왔을 때, stack의 top이 num과 같지 않으면, 정상적으로 수열이 만들어지지 않는다.

처음엔 입력을 input으로 받았다가 시간이 너무 오래 걸려서
sys.stdin.readline()으로 받았다.

4120ms > 228ms 로 시간이 단축됐다