[백준 1874][파이썬] 스택 수열

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

1874번: 스택 수열

스택을 이용하는 문제.

 

어렵지는 않지만 여러가지 상황들을 고려하는 것이 까다로웠던 문제이다.

 

나는 다음 세 변수들을 생성하여 서로 값을 비교하면서 문제를 풀었다.

 

1. 마지막으로 스택에 넣은 값 (이 값은 무조건 1씩 증가)
2. 현재 스택의 가장 위에 있는 값
3. 입력 값

다음과 같은 상황들을 고려하면 된다. 

 

입력 값(3번)이 마지막으로 스택에 넣은 값(1번)보다 같거나 크다면?

 

이럴 경우 3번과 값이 같아질 때까지 1번의 값을 증가시키면서 스택에 push한다.

 

같아진다면 pop을 한다.

 

입력 값(3번)이 마지막으로 스택에 넣은 값(1번)보다 작다면?

 

이럴 경우 3번 값은 이미 스택에 들어간 적이 있다는 뜻이다.

 

그러면 나올 때까지 pop을 하면 된다.

 

그런데 스택이 빌 때까지 나오지 않았다면 이미 pop이 되었다는 뜻이고 NO를 출력하면 된다.

 

위 과정들을 반복하면 된다.

 

<최종 코드>

import sys
# 입력으로 들어온 값이 last_input보다 작으면?
#     =>stack[-1]값과 입력값 비교 입력값이 더 크거나 스택이 비어있으면?
#         =>불가능
#     =>아니면?
#         =>나올때까지 pop하기
#          =>계속 stack[-1]과 비교
# 크면?
#     =>last_input 증가시키면서 스택에 넣기
n=int(sys.stdin.readline())
last_input=1
stack=[]
res=''
for _ in range(n):
    temp=int(sys.stdin.readline())
    if temp>=last_input:
        while last_input<=temp:
            stack.append(last_input)
            last_input+=1
            res+='+'
        stack.pop()
        res+='-'
    else:
        if len(stack)==0:
            print("NO")
            exit()
        else:
            while stack.pop()!=temp:
                res+='-'
                if len(stack)==0:#다 꺼냈는데 안 나옴
                    print("NO")
                    exit()
            #통과했다는건 나왔다는 뜻
            res+='-'
for i in res:
    print(i)