[백준] 2493 파이썬(python) : 탑 - (monotone stack 알고리즘)

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

2493번: 탑

 

 

단조스택 문제다. 오른쪽에서 부터 보기 시작하면 오름차순이지만 왼쪽에서 보면 내림차순이다. 결국 원소의 위치 그러니까 인덱스를 출력해줘야 하는 문제여서 stack에 값이 아닌 인덱스를 삽입해준다.

 

import sys
n = int(sys.stdin.readline())
tower = list(map(int, sys.stdin.readline().split()))
res, stack = [0]*n, [] #1
for idx in range(n): #2
    while stack and tower[stack[-1]] < tower[idx]: #3 내림차순
        stack.pop()
    if stack: #4
        res[idx] = stack[-1] + 1
    stack.append(idx)
print(*res)

 

#1 : 결과 리스트와 stack 선언

#2 : 왼쪽에서부터 순환

#3 : monotone stack 알고리즘의 내림차순 유지

#4 : 인덱스를 출력하는거니까 자신이 레이저를 보낼 수 있는 탑의 위치를 저장

 

1. 단조스택은 stack리스트가 내림차순이든 오름차순이든 단조로운것

2. stack만 삽입, 삭제가 가능하다.

 

---

17298번 : 오큰수

6190번 : 옥상 정원 꾸미기