[BOJ] 1874번: 스택 수열 (python)

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

💡 해결 방법

• list의 del 기능이 해당 인덱스 삭제하면서 뒤의 인덱스가 한 칸씩 앞으로 당겨지는 동작이 시간을 많이 잡아먹는다는 사실을 간과했다.
• 처음에는 두 번째 코드에 del 넣어서 작성했다가 시간초과 나고 첫 번째 코드로 수정하였다.
• 입력 받으면서 stack에 push/pop하는 동작을 동시에 수행하여 시간을 줄였다.

🖥️ 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
stack = []
arr = [i for i in range(1, n+1)]
result = ""
no = False

for i in range(n):
    input = int(sys.stdin.readline())
    while len(arr) >= 1 and arr[0] <= input:
        stack.append(arr[0])
        del arr[0]
        result += "+\n"

    if stack[-1] == input:
        stack.pop()
        result += "-\n"
    else:
        no = True
        break
if no:
    print("NO")
else:
    print(result.rstrip())

🖥️ 코드2

import sys

n = int(sys.stdin.readline())
stack = []
arr = [i for i in range(1, n+1)]
result = ""
no = False
idx = 0
input = []

for i in range(n):
    input.append(int(sys.stdin.readline()))

#arr 값 하나씩 집어넣기
for i in range(len(arr)):
    stack.append(arr[i])
    result += "+\n"
    while stack:
        if input[idx] == stack[-1]:
            result += "-\n"
            stack.pop()
            idx += 1
        else:
            break
    
#stack에 값 꺼내야함
while stack:
    if input[idx] == stack[-1]:
        result += "-\n"
        stack.pop()
        idx += 1

    else:
        no = True
        break
if no:
    print("NO")
else:
    print(result.rstrip())

✏️ 알고리즘 분류

• 자료 구조
• 스택