[백준] 1874: 스택 수열 (python 파이썬)

1874번: 스택 수열

스택 수열 문제는 stack의 push와 pop 연산을 조합하여 1~n까지의 숫자를 원하는 수열의 형태로 뽑아내는 방법을 출력하는 문제다. 이때 push는 +, pop은 -로 출력한다. 예를 들어, 1~5로 만들 수 있는 수열 중 "4 3 5 2 1"을 만들고 싶다면 "push push push push pop pop push pop pop pop"을 수행하면 된다. 이를 +, -로 표현해주는 것이 문제의 요구사항이다.

 

해당 문제를 풀기 위해 생각한 알고리즘은 다음과 같다.

• 우리는 1~n을 순서대로 입력받는다. 이때 1~n을 차례로 입력받으며 푸쉬하다가, 수열의 첫째 자리 수(0번째 인덱스)와 동일한 수가 나오면 pop을 수행한다. 이후 다른 수를 push하기 전에 이전에 push한 값이 다음 번 인덱스(1번째 인덱스)와 같은지 체크해야 한다. 만약 같으면 그 다음 번 인덱스도 체크해주면 되고, 아니라면 다음 번 수를 push하고 위 과정을 반복하면 된다.

코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input())

stack = list()
result = list()
progression = list()

for _ in range(n):
    progression.append(int(input()))

searching_index = 0
for i in range(1, n+1):
    stack.append(i)
    result.append('+')
    
    '''
    (아래 조건문은 필수는 아니다. n도 그닥 큰 수가 아니라 성능 향상이 되진 않는다.)
    사실 push한 값보다 다음에 탐색해야할 값이 크다면 해당 수열은 해결할 수 없다.
    왜냐하면 현재 푸시한 값 이후에 푸시되는 값들은 모두 현재 값보다 크다.
    즉, 현재 수열에서 나와야하는 숫자는 절대 나올 수가 없다.
    '''
    if i > progression[searching_index]:
        break
    
    while len(stack) > 0:
        if stack[-1] == progression[searching_index]:
            stack.pop()
            result.append('-')
            searching_index += 1
        else:
            break

if len(stack) == 0:
    print('\n'.join(result))
else:
    print("NO")