[Python] 백준/BOJ 1874번: 스택 수열 (Silver 2)

💻 Problem

문제 보러 가기

 

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

 

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1 이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

 

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push 연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

 

💡 Approach

처음에 문제를 이해하기가 어려웠다.

연산 과정이 뭔 소린지.. 그래서 그 부분을 찾아서 이해하고 풀었다.

나는 1부터 n까지의 숫자를 하나씩 스택에 push, pop 연산을 할 수 있다.

그리고 그 스택에 있는 숫자를 활용해 입력된 수열을 만들면 된다.

 

다음은 내가 이해하려고 살펴본 연산 과정이다.

백준의 예제 입력 1로 연산 과정을 살펴보겠다.

 

연산 과정 살펴보기 ⤵️

0. 초기 상태

• 스택: []
• 수열: [4, 3, 6, 8, 7, 5, 2, 1]
• 연산 결과: []

 

1. 수열의 첫 번째 숫자 = 4

• 1부터 4까지 차례대로 push(+):
  • push(1): 스택 = [1], 연산 = ['+']
  • push(2): 스택 = [1, 2], 연산 = ['+', '+']
  • push(3): 스택 = [1, 2, 3], 연산 = ['+', '+', '+']
  • push(4): 스택 = [1, 2, 3, 4], 연산 = ['+', '+', '+', '+']
• 스택 맨 위 숫자 4 pop(-):
  • 스택 = [1, 2, 3], 연산 = ['+', '+', '+', '+', '-']

 

2. 수열의 두 번째 숫자 = 3

• 스택 맨 위 숫자 3 pop(-):
  • 스택 = [1, 2], 연산 = ['+', '+', '+', '+', '-', '-']

 

3. 수열의 세 번째 숫자 = 6

• 5와 6을 push(+):
  • push(5): 스택 = [1, 2, 5], 연산 = ['+', '+', '+', '+', '-', '-', '+']
  • push(6): 스택 = [1, 2, 5, 6], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+']
• 스택 맨 위 숫자 6 pop(-):
  • 스택 = [1, 2, 5], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-']

 

4. 수열의 네 번째 숫자 = 8

• 7과 8을 push(+):
  • push(7): 스택 = [1, 2, 5, 7], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+']
  • push(8): 스택 = [1, 2, 5, 7, 8], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+']
• 스택 맨 위 숫자 8 pop(-):
  • 스택 = [1, 2, 5, 7], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+', '-']

 

5. 수열의 다섯 번째 숫자 = 7

• 스택 맨 위 숫자 7 pop(-):
  • 스택 = [1, 2, 5], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+', '-', '-']

 

6. 수열의 여섯 번째 숫자 = 5

• 스택 맨 위 숫자 5 pop(-):
  • 스택 = [1, 2], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+', '-', '-', '-']

 

7. 수열의 일곱 번째 숫자 = 2

• 스택 맨 위 숫자 2 pop(-):
  • 스택 = [1], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+', '-', '-', '-', '-']

 

8. 수열의 여덟 번째 숫자 = 1

• 스택 맨 위 숫자 1 pop(-):
  • 스택 = [], 연산 = ['+', '+', '+', '+', '-', '-', '+', '+', '-', '+', '+', '-', '-', '-', '-', '-']

 

✏️ Solution

import sys
input = sys.stdin.readline

n = int(input())
st = []
op = []
cur = 1

for _ in range(n):
    num = int(input())

    # cur이 입력받은 숫자와 작거나 같다면 push
    while cur <= num:
        st.append(cur)
        op.append('+')
        cur += 1
    
    # 스택의 top이 입력받은 숫자와 같다면 pop
    if st[-1] == num:
        st.pop()
        op.append('-')

    else:
        print('NO')
        break
    
if not st:
    print("\n".join(op))

 

스택의 top이 입력받은 숫자와 다르다면 수열을 만들 수 없는 경우이다.

반복문이 끝난 후 수열이 완성된다면 모든 숫자를 사용한 것이므로 스택이 비어있을 것이다.