1874 stack 수열

문제

이 문제를 이해하는데 좀 어려웠다. 개인적으로 어려웠던 것 뿐이지만, 간단한 설명을 진행해보겠다.

stack 구조에 맞춰서 들어온 숫자들이 순차적으로 push pop이 될 수 있는지 체크하는 것이 관건이다.

8 -> 8개의 input이 들어올 예정 
4 -> 먼저 4가 출력되어야 한다. 
3 -> 3이 출력 
6 -> 6이 출력 
8 ...
7 ... 
5 ...
2 ...
1 ... -> 마지막으로 1이 출력 

---------------------------------------------
+ -> 1 입력 
+ -> 2 입력 
+ -> 3 입력
+ -> 먼저 4까지 들어온다
- -> 4가 출력. 
- -> 3이 출력
+ -> 5 입력 
+ -> 6 입력
- -> 6 출력 
+ -> 7 입력 
+ -> 8 입력
- -> 8 출력 
- -> 7 출력 
- -> 5 출력 
- -> 2 출력 
- -> 1 출력

	input과 output의 규칙을 파악해보면, 입력값으로 4가 들어온 시점에서 이미 4가 push 되고 나서 pop되는 시점이라는 뜻이다. 

처음에 문제를 풀려고 했을 때 stack의 상태를 확인하는 함수 1개만 만들어서 문제를 풀려고 했다. 현재 top의 값을 업데이트 해주는 기능과 비슷한 함수를 만들려고 했다.
하지만 4라는 input 값이 들어왔을 때

1. stack 상태 -> [1,2,3,4] (top이 맨 뒤를 가정한다.)

2. 이후 바로 4가 빠져야하므로 '-' 가 출력해야 하는 상황이다.

그렇기 때문에 push를 담당하는 함수와 pop을 해주는 함수 2개를 만들었다

import sys 
import collections 

result_stack = []
n = int(input())
status_stack = collections.deque([0])
max_val = status_stack[-1]

def push_stack(current):
    global max_val
    if status_stack and status_stack[-1] < current:
            
        while max_val < current: # 5<6 에서 6 더해지므로 < 
            status_stack.append(max_val+1)
            max_val+=1 
            result_stack.append('+')
            
def pop_stack(current, final_flag):
    if final_flag and status_stack[-1] == current:
            
        result_stack.append('-')
        status_stack.pop()
        return True 
    return False
        
final_flag = True 
for i in range(n):
    current = int(sys.stdin.readline())
    push_stack(current) 
    final_flag &= pop_stack(current, final_flag)
if final_flag == False:
        print("NO")
        sys.exit()
for state in result_stack:
    print(state)

2번째 테스트 케이스에 대해서 왜 NO인지 설명해보자면

5 -> 5개 입력
1 
	[0,1] 상태에서 1 pop 후 현재 [0]
2
    2 push 후 [0,2]에서 2 pop 후 현재 [0]
5
	5까지 push하면 [0,3,4,5]에서 5 pop 후 현재 [0,3,4]
3
    현재 top의 값이 4인데 3 pop 하려고 하면 잘못된 수열 이므로 pop_stack함수에서 False return 
4
    4 pop_stack 함수에서 if 문 충족이 안되서 return False

이렇게 나오는 것을 볼 수 있다.

결론적으로 pop_stack과 push_stack 함수를 합쳐서 구현하면 복잡하게 구현할 것 같아서 n이라는 값이 입력되면 n까지 입력되는 함수와 n을 뽑는 함수를 구현했다는 것이 이번 문제를 풀어낸 방법이라고 생각한다