1874: 스택 수열 - Python

문제

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

풀이 1 (내 풀이)

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]
stack = []
output = []

for i in range(1, n+1):
    stack.append(i)
    output.append("+")
    while stack:
        if stack[-1] == arr[0]:
            stack.pop()
            arr.pop(0)
            output.append("-")
        else:
            break

if len(output) == 2 * n:
    print("\n".join(output))
else:
    print("NO")

• arr: 입력한 수열
• stack: 스택
• output: 출력할 +, -가 순서대로 저장됨

1. 1부터 n+1까지 순회하며 stack에 i를 push (output에 "+" 추가)
2. stack에 값이 존재하면, stack의 마지막 원소와 arr의 첫번째 원소를 비교
   -> 값이 같을 경우, 해당 값을 pop하고 output에 "-" 추가
3. for문 종료 후, output 검사
   -> output의 길이가 2*n이라면 정상이므로 output 출력
   -> 그렇지 않다면 비정상이므로 "NO" 출력

직관적으로 이해가 되는 풀이는 아닌 것 같다.

풀이 2 (GPT o1)

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]

stack = []
output = []
now = 1
possible = True

for num in arr:
    while now <= num:
        stack.append(now)
        output.append("+")
        now += 1

    if stack and stack[-1] == num:
        stack.pop()
        output.append("-")
    else:
        possible = False
        break

if possible:
    print("\n".join(output))
else:
    print("NO")

• GPT 형님이 8배나 빠른 코드를 작성해주셨다.