2493번 탑

문제 출처 : https://www.acmicpc.net/problem/2493

사고과정

빗물이나 유사한 느낌의 다른 문제를 떠올리면서 풀은 것 같다.
정말 단순하게 생각해보자.

"왼쪽에 나보다 큰 탑이 있으면 그 탑의 INDEX들로 바뀐다."

그렇다면 그게 어디에 있는지 어떻게 찾을 것인지 코드로 구현하면 되겠다.
"왼쪽에 나보다 큰 탑이 없으면 (현재 탑의 인덱스를 i라 하자.) i의 값은 0이 된다." 그렇기 때문에 만약 INDEX를 0에서부터 시작했을 때 계속 상승한다면 모든 값이 0이 될 것이다. 그렇다면 변화하는 지점은 탑의 높이가 작아졌을 때! "작아진다면 i의 값은 i-1이 된다."
하지만 다시 커지는 경우( i+1 )가 발생할 것이다.
이럴 경우 어떻게 해야하지? 이전에 있던 큰 탑들과 비교했을 때 어디까지 커지지? i-1의 탑보다 작을 수도 있고 클 수도 있다. 상승한다 하더라도 i-1의 탑보다 작다면 어차피 기껏해야 i-1이다. 근데 만약 i-1의 탑보다 커진다면? 그 이전에 있던 큰 탑에 대한 정보가 필요하다.

" 탑이 작아질때마다 탑의 크기와 index를 갱신해야겠다. "
왜냐? 탑이 작아진다는 건 왼쪽에 벽이 생긴다(max) 라고 생각할 수 있다. 이걸 뛰어넘지 못한다면 결과는 기껏해야 그 벽(max)이다. 만약 더 이상 벽이 존재하지 않는다면 새로운 벽이 생긴거지.

import sys

N = int(sys.stdin.readline().rstrip("\n"))

top = [0]+list(map(int,sys.stdin.readline().rstrip("\n").split()))
result = [0]*(N+1)
top_height=[]
top_index=[]

for i in range(1,N+1) :
    if top[i-1]>=top[i] : # 탑이 작아질 때, 계단처럼
        result[i]=i-1
        top_height.append(top[i-1])
        top_index.append(i-1)
    elif top[i-1]<top[i] : # 탑이 커질 때
        if not top_height : # 이전에 하락이 없다. => 0
            continue
        last_height = top_height.pop()  # 이전에 하락 존재
        last_index = top_index.pop()
        while last_height < top[i]: # 이전 탑보다 현재 탑이 더 크다면 반복. 얼마나 큰지 확인
            if not top_height : # 이전에 나보다 큰 탑이 없다. 새로운 max
                last_height = 0
                break
            last_height = top_height.pop() 
            last_index = top_index.pop()
        if last_height : #이전 큰 탑
            result[i]=last_index
            top_height.append(last_height)
            top_index.append(last_index)
            
print(" ".join(map(str,result[1:])))

엄청 간결하게 푸셔서 참고. ( whale11님 )

N = int(input())
_input = list(map(int,input().split()))


_stack = []
_out = [0] * N

for i in range(N-1,-1,-1):
    while _stack and _input[_stack[-1]] < _input[i] :
        idx = _stack.pop()
        _out[idx] = i + 1
    _stack.append(i)

while _stack:
    i = _stack.pop()
    _out[i] = 0

print(*_out)