[자료구조/스택] 백준 1874 스택 수열 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1874번: 스택 수열

 

 

 

2. 문제 풀이

 스택을 이용한 수열이 가능한지 검증하는 문제입니다. 스택에는 1부터 N까지의 숫자가 입력되며, push와 pop 연산으로 제시된 수열을 만들어야 합니다.

 

2022.02.10 - [Algorithm] - [Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

 위 링크의 스택 구조를 이용하면 쉽습니다. 수열의 숫자만큼 스택에 push한다음, pop하면 됩니다. 만약 수열의 숫자가 pop되는 숫자 또는 push할 숫자보다 작으면 해당 수열은 만들 수 없습니다. 

 

 

 

3. 코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
stack = deque([1]) #스택
operation = ['+'] #스택연산
cnt = 1 #최대 n까지
impossible = False

for i in range(n):
     x = int(input())

     # x가 클 경우 더하기
     while cnt < x:
         cnt += 1
         stack.append(cnt)
         operation.append('+')

     # 맨 위에 x가 있을 시 꺼내기
     if len(stack) != 0 and stack[-1] == x:
         stack.pop()
         operation.append('-')

     # 그 외에는 안되는 수열
     else:
         impossible = True

if impossible:
    print("NO")
else:
    print("\n".join(operation))

 수열이 안된다고 break로 바로 빠져나오면 입력 수열을 모두 받지 못합니다. 체크만 해두고, 나중에 출력합니다.