[백준 1874번] 스택 수열 Python 풀이

Python 문제풀이

n = int(input()) # 수열의 요소 개수
x=[] # 입력받은 수열
y=[0] # 작업할 스택 공간, 0을 넣어준 이유는 y[-1]을 했을때 범위 오류 방지용
result=[] # +,- 등의 결과를 저장할 리스트

# 수열을 입력받는다
for i in range(n):
    x.append(int(input()))

current=0 # push되는 스택의 현재 수
for i in range(n):
    if y[-1]<x[i]: # 스택의 top에 위치한 값이 수열 값보다 작다면
        while current<x[i]: # push되는 스택의 현재 수가 수열 값과 같아질때까지 push한다
            current += 1
            y.append(current) #push 작업
            result.append('+')
        y.pop() # 수열에 입력된 값이라는 뜻은 결국 pop을 당했던 것이기 때문에 해준다.
        result.append('-')

    elif y[-1]==x[i]: # 스택의 top에 위치한 값이 수열 값과 같다면
        y.pop() # 그대로 pop해준다
        result.append('-')
    else: # 스택의 top에 위치한 값이 수열 값보다 크다면
        print('NO') # 직접 해보면 알겠지만 이 경우가 NO를 출력해야하는 경우이다
        exit()

for i in range(len(result)): # 결과를 출력한다
    print(result[i])

1차로 문제 이해가 안가서 고전하다가 2차로 구현에서 고전했는데.. 뭐든 원리에서 답이 나오는것같습니다.

 

주석으로 설명을 쓰긴 했지만 핵심 부분을 설명하겠습니다.

 

- 수열에 입력된 값은 pop이 되면서 입력된 값들이다. 수열에 입력된 값에 도달하는 순간 그 값은 pop을 당해야 한다.

  : 그렇기 때문에 수열이 현재 스택의 top 값보다 큰 값을 요청했다면 그 값까지 push를 한 뒤 pop을 한 번 당한것이다.

 

- push작업이 필요한게 아닌 경우라면 항상 top의 값과 수열의 요청값이 같을것이다.

  : 이 문제에서는 push와 pop만 진행하는데 push작업이 필요한 경우는 수열이 현재 스택의 top 값보다 큰 값을 요청했을 경우이다. 더 추가를 해야하는 경우가 아니라면 빼는 pop 작업밖에 없다. 근데 스택은 빼는 작업을 항상 top에서만 진행하기 때문에 pop작업을 요청했다면 항상 top과 수열의 요청값이 같다.

 

- 그렇다면 수열에 입력된 값이 top 값보다 작은 경우는 어떻게 되는가?

  : 그 경우가 스택이 깨지는 순간이다. 'NO'를 출력하면 된다. 스택은 top에있는 값만을 pop할 수 있는데 top 값을 무시하고 그 속에있는 값을 요청하는 꼴이기 때문이다.