[Python] BOJ/백준 1874번 스택 수열

[문제]

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

1874번: 스택 수열

 

[풀이]

재밌는 문제였다. (내가 한 번에 풀면 재밌는 문제 아니면 재미없는 문제 ^^~)

 

stack은 숫자 값을,  result는 '+' 혹은 '-' 값을 담을 리스트이다.

 

next_turn은 pop한 뒤 다시 숫자를 쌓기 시작할 때 어느 수부터 쌓는지 기억하는 변수이다.

예를 들어 1, 2, 3, 4를 append 한 후 차례대로 4를 pop, 3을 pop 했다. 그 후 다시 숫자를 쌓아야 할 때는 5부터 쌓기 시작한다. next_turn은 숫자 5를 저장하는 변수이다. 숫자는 1부터 쌓기 시작하니 1로 초기화해주었다.

 

flag는 예제대로 나오기 불가능한 경우에 False값이 된다.

---

1. 순서대로 나와야하는 수열을 sequence 리스트로 만들어놓는다.
2. 첫 번째 줄에서 받은 입력값 n을 기준으로, sequence를 차례대로 돈다.
3. stack이 비어있거나 sequence[i] 보다 stack의 마지막 값이 작은 경우 
   
   1. 쌓아야 하는 숫자부터 현재 차례인 sequence값+1 만큼 stack에 추가한다.
   2. result에는 '+'를 추가한다.
   3. next_turn를  sequence+1 값으로 덮어씀
4. stack의 마지막 값이 sequence[i] 보다 큰 경우
   1. flag를 False로 변경
   2. 반복문 탈출
5. stack의 마지막 값과 sequence[i]가 같은 경우
   1. stack의 마지막 값을 꺼낸다.
   2. result에는 '-' 추가
6. flag가 True면 결과 출력, False면 "NO"출력

 

[코드]

import sys

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    sequence = [int(sys.stdin.readline()) for _ in range(n)]

    stack = []
    result = []
    next_turn = 1
    flag = True
    for i in range(n):
        # 스택에 아무 값도 없을 때 혹은
        # 스택 마지막 값이 현재 pop 되어야 할 값보다 작을 때
        if len(stack) == 0 or stack[-1] < sequence[i]:
            for j in range(next_turn, sequence[i] + 1):
                stack.append(j)
                result.append("+")
            next_turn = sequence[i] + 1
        # 스택 마지막 값이 현재 pop 되어야 할 값보다 클 때
        elif stack[-1] > sequence[i]:
            flag = False
            break

        # 스택 마지막 값 == 현재 pop 되어야 할 값
        if stack[-1] == sequence[i]:
            stack.pop()
            result.append("-")

    if flag:
        print("\n".join(result))
    else:
        print("NO")