[Python] BOJ 1874번: 스택 수열

1874번: 스택 수열

배경

특별히 문제가 어렵다는 것은 아니고,
문제에 기술된 정의 그대로 자료구조를 설계한다는 목적에 사로잡혀

최적화를 놓친 경우를 기록하고자 한다.

---

1차 시도

코드 전문

import sys

arr = list(map(int, sys.stdin.readlines()))

IN = [n for n in range(1, arr[0] + 1)]
stack = [0]
res = []

for ar in arr[1:]:
    while stack[-1] < ar:
        res.append('+')
        stack.append(IN.pop(0))

    if stack[-1] == ar:
        res.append('-')
        stack.pop(-1)
    else:
        break

if len(IN) == 0 and len(stack) == 1:
    print(*res, sep='\n')
else:
    print('NO')

1부터 N까지 순차적으로 나열된 숫자로부터의 연산을 진행하기 위해

IN = [n for n in range(1, N+1)] 형태로 배열을 선언하고

이후 IN.pop(0)를 통해 뽑아쓰는 것이 화근이었다.

pop 연산은 단순히 값을 읽어오는 것뿐만 아니라 자료구조의 형태를 변화시키므로 비싼 연산임을 명심하자.

---

2차 시도

코드 전문

import sys

arr = list(map(int, sys.stdin.readlines()))

IN = 1
stack = [0]
res = []

for ar in arr[1:]:
    while stack[-1] < ar:
        res.append('+')
        stack.append(IN)
        IN += 1

    if stack[-1] == ar:
        res.append('-')
        stack.pop(-1)
    else:
        break

if IN == arr[0] + 1 and len(stack) == 1:
    print(*res, sep='\n')
else:
    print('NO')

어차피 순서대로 증가시키며 입력하는 과정을 반복하는 것이므로

IN = 1로 설정하고, IN을 입력한 후, IN += 1로 증가시켰다.