[백준 BOJ] 1874번 스택 수열 (파이썬 Python)

문제 설명

 

첫 출에 입력으로 들어올 n이 주어진다. 

둘째 줄부터 수열을 이루는 정수가 하나씩 순서대로 주어지고, 숫자는 중복없이 한번 씩만 나온다.

 

예제의 경우 다음과 같이 입력이 주어진다.

8
4
3
6
8
7
5
2
1

 

 

 

 

첫 줄에 8(n)이 등장하고, 8개의 숫자가 있다.

 

첫 숫자는 4이고, 스택에는 오름차순으로 숫자를 push하기 때문에, 다음과 같은 연산이 실행된다.

 

stack = [1, 2, 3, 4]    push, push, push, push

 

 

push 연산 후 pop 연산을 실행해, stack의 마지막 숫자인 4를 꺼내 수열을 만든다.

 

stack = [1, 2, 3, 4]    (pop)    [1, 2, 3]

sequence = [4]

 

 

다음 숫자는 3이기 때문에 추가적인 push 없이 한번의 pop을 실행한다.

 

stack = [1, 2, 3]    (pop)    [1, 2]

sequence = [4, 3]

 

 

세번 째 숫자는 6이다.

현재 오름차순으로 4까지 push한 상태이기 때문에, 5부터 6까지 push한다.

 

stack = [1, 2]    (push, push, push, push)    [1, 2, 5, 6]

 

 

마찬가지로 수열을 생성해야 하기 때문에, 마지막 숫자인 6를 꺼낸다.

 

stack = [1, 2, 5, 6]    (pop)    [1, 2, 5]

sequence = [4, 3, 6]

 

 

위와 같은 과정을 반복하며 최종적인 수열을 만들어 낸다.

 

 

 

코드

import sys

input = sys.stdin.readline

n = int(input())

stack = []
answer = []
cur = 1  # current

for i in range(n):
   num = int(input())
   
   while cur <= num:
      stack.append(cur)
      answer.append('+')
      cur += 1

   if stack[-1] == num:
      stack.pop()
      answer.append('-')
   else:
      print('NO')
      break

else:
   for i in answer:
      print(i)

 

 

정답 코드는 아래 블로그를 참조하였다.

https://hongcoding.tistory.com/39

 

 

 

 

문제 출처: https://www.acmicpc.net/problem/1874

1874번: 스택 수열