[Python/백준] 2493 탑

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

2493번: 탑

<문제 해설>

stack을 사용하는 문제이다.

stack에 현재 타워에서 보이는 왼쪽 빌딩들을 저장해 나가면서 풀어나가면 된다.

stack에는 타워의 높이와 타워의 위치를 저장한다.

1. 처음 stack에는 0번째 타워의 크기와 위치를 저장해둔다. 첫타워는 왼쪽에 타워가 없어 무조건 0이 출력되니 output에도 0을 넣어둔다.
2. 1 부터 N까지 for문을 돌려서 모든 타워를 계산한다.
3. stack이 빌때까지 혹은 break를 당할때까지 반복문을 준다.
4. stack의 마지막 값이 (왼쪽에 보이는 가장 작은 값이) 현제 타워보다 작거나 같으면 현제 타워에 가려지니 stack.pop해서 값 제거한다. 다시 3번으로
   stack의 마지막 값이 현제 타워보다 크다면 마지막값의 타워가 레이저를 수신한거니 output에 그 타워의 위치를 넣어주고 stack에도 현제 타워의 크기와 위치정보를 넣어준다. 반복문 종료
5. 만약 스텍이 4번의 첫 행동으로 인해 다비어버렸다면 현제 타워보다 큰 왼쪽 타워가 없다는 것이니 0을 output에 넣어주고 stack에도 현제 타워의 높이와 위치를 저장해준다.
6. 모든 일이 끝나고 output을 출력해준다.

<예시>

예시1을 보여주겠다.

타위 크기 그림

위 그림은 빌딩의 크기를 n에 따라서 나타냈다.

n값에 따른 stack과 output

n값이 변함에 따라 stack이랑 output이 어떻게 변하는지 나타냈다.

1. n = 0 stack에는 6이랑 output은 0이 들어갔다,
2. n= 1 stack[-1]의 6보다 현제 타워의 크기가 더 크니까 stack을  9로 바꾸고 output에도 0을 넣어준다.
3. n = 2 stack[-1]의 9가 현제 타워보다 크니까 stack에 현제타워 크기 5를 넣어준고 output에 9의 위치인 2를 넣어준다.
4. n = 3 stack[-1]의 5가 현제 타워보다 작으니까 stack을 한번 pop한다. 그러고나면 stack[-1]은 9가 되어 현제 타워보다 크니까 현제타워를 stack에 넣고 output에 9의 위치를 넣어준다.

<코드>

import sys

N = int(sys.stdin.readline())
towers = list(map(int,sys.stdin.readline().split()))
stack = [[towers[0],0]]
output = [0]
for n in range(1,N):
    while(stack):
        if stack[-1][0] <= towers[n]:
            stack.pop()
        else:
            output.append(stack[-1][1]+1)
            stack.append([towers[n],n])
            break
    if len(stack) == 0:
        stack.append([towers[n], n])
        output.append(0)
print(*output)