[백준 1874][Stack][파이썬] 스택 수열 - 풀이 및 답안

문제

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

 

풀이

목적은 Stack에 입력받는 1 ~ N 까지의 수를 무작위로 중복되지 않게 입력값을 주었을 때 남김없이 Push, Pop 연산을 통해 스택을 비울수 있는를 묻는 문제이다. 

 

(입력 예제 1.) 수열이 성립하는 경우

규칙에 따라 Push 연산과 Pop 연산을 수행 하였을 때, Stack은 모두 비워지고, 1~8까지의 모든 수가 Stack을 걸쳐 나갈 수 있다. 이 때 수열이 성립한다고 이 문제에서 정의한다.

 

 

(입력 예제 2.) 수열이 성립하지 않는 경우

아래 경우, Input 3 과정에서, 이미 4라는 숫자가 추가되고 제외되었다. 5라는 숫자까지 진행했기에 4라는 숫자를 입력받았을 때 Pop(-) 연산이 작용되어야 한다. 그러나, Stack은 비워져 있기에 Push(+) 연산을 작용해야 하는데 이는 문제 조건의 오름차순 조건에 위배된다.

 

답안 코드

import sys

# N 입력받기
N = int(input())


current =0
stack=[0]
answer=[]

# 수열 입력받기
for _ in range(N):
    
    # Boundary Condition (stack, current, target)
    target = int(sys.stdin.readline().strip())
    
    # (+) When current < target
    while current < target:
        current += 1
        stack.append(current)
        answer.append('+')

        # Current = Target 에 도달했을 때 마지막 값을 빼줌
        if current ==target:
            stack.pop()
            answer.append('-')

    # Current 값이 Target 값보다 작은 경우 
    if current > target:

        #오름차순 수열에 위반되는 경우 i.e current > target인데, Push(+)가 수행되는 경우
        if stack[-1] < target:
            stack.append(-1)
            break

        while stack[-1] >= target:
            stack.pop()
            answer.append('-')

# 답 출력
if len(stack) !=1:
    answer = 'NO'
    print(answer)

else:
    for method in answer:
        print(method)