[스택] 백준 #1874 스택 수열 - python

🗂️ 문제

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

 

💡 접근법

제시하는 입력값의 수열을 만들기 위해 1~N까지 차례로 숫자가 입력될 때 스택에서 어떤 순서로 push와 pop을 해야할 지를 결정해야 하는 문제이다.

 

풀이는 다음과 같다.

 

1부터 N까지 숫자를 차례대로 입력한다.

• 스택의 top이 현재 비교하는 수열보다 작다면 현재 숫자를 스택에 push한다.
• 스택의 top이 현재 비교하는 수열과 같다면 스택에서 pop하고, 반복 수행한다.
  위 과정을 while 문을 통해 반복 수행하는 이유는, pop한 뒤 수열의 top과 다음 수열이 같을 수 있기 때문이다.

모든 숫자를 입력한 뒤 만약 스택이 비어있다면 만들 수 있는 수열이 되고, 스택이 비어있지 않다면 만들 수 없는 수열에 해당한다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())
arr = [int(sys.stdin.readline()) for _ in range(N)]  # 만들고자 하는 수열

stack = []
print_stack = []

j = 0
for i in range(1, N+1):  # 1 ~ N까지의 숫자 입력
    if not stack or stack[-1] < arr[j]:  # 스택의 top이 현재 비교하는 수열보다 작다면
        stack.append(i)
        print_stack.append('+')
    
    while stack and stack[-1] == arr[j]:  # 스택의 top이 현재 비교하는 수열과 같다면
        stack.pop()
        print_stack.append('-')
        j += 1

if stack:
    print("NO")
else:
    for p in print_stack:
        print(p)

 

✅ 정답 확인