백준 6549 [python]

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

import sys

while True:
    h = list(map(int, sys.stdin.readline().split()))
    n = h.pop(0)
    res = 0
    if n == 0: exit()
    
    stk = [[-1, 0]]
    for i in range(n):
        while h[i] < stk[-1][1]:
            idx, height = stk.pop()
            index = stk[-1][0] + 1
            res = max(res, (i - index) * height)
        if h[i] == stk[-1][1]: stk[-1][0] = i
        stk.append([i, h[i]])
    
    while len(stk) > 1:
        idx, height = stk.pop()
        res = max(res, (n - stk[-1][0] - 1) * height)
        
    print(res)

스택에 저장된 원소는 그 높이를 가진 정답인 직사각형이 존재할 가능성이 아직 있는 블럭이다.
스택 안의 원소보다 높이가 작은놈을 만났을 때, 높이가 작은놈은 스택을 차례대로 돌며 자기보다 큰 높이를 가진 블럭으로 만들 수 있는 직사각형의 넓이를 최댓값에 갱신하고, 그렇게 되면 더 이상의 가능성이 남아있지 않으므로 포기시킨다.

for 문을 돌고 나면 스택에는 오름차순으로 가능성이 남아있는 블럭들이 존재한다. 그 블럭들은 끝까지 검사했음에도 본인보다 작은놈이 나타나지 않아 가능성을 포기당하지 않았기 때문에 그대로 최댓값에 갱신하면 된다.

구글링하다 멋있는 풀이를 찾았다.
https://990427.tistory.com/41

내 코드의 아쉬운 점은, 스택에 넣는 인덱스를 그냥 처음에 받은 배열의 인덱스 그대로 사용한 것이다. 이 때문에 중간에 인덱스를 다시 계산하는 줄이 추가됐다. 높이가 겹치는 놈이 스택에 쌓이는 것을 피하기 위한 코드도 추가해야 했다.

input 블럭이 0 5 2 2일 때, 인덱스 1번 블럭이 pop되고 인덱스 2번 블럭이 스택에 추가될 때 인덱스를 바꿔서 (1, 2)를 스택에 추가한다면, 그 인덱스의 의미는 해당 높이를 가진 직사각형의 출발점이고, 그 블럭이 pop될 때 직사각형의 넓이를 아래 스택의 블럭을 참조하지 않고 구할 수 있게 되어 코드가 간결해진다.

이 사람은 블럭 리스트 끝에 0을 추가해서 스택에 남은 블럭들을 빼는 코드를 쓰지 않고도 스택에 남는 블럭이 모두 빠져나가게 만들었다..

import sys

while True:
    h = list(map(int, sys.stdin.readline().split())) + [0]
    n = h.pop(0)
    res = 0
    if n == 0: exit()
    
    stk = [(-1, 0)]
    for i in range(n + 1):
        idx = i
        while h[i] < stk[-1][1]:
            idx, height = stk.pop()
            res = max(res, (i - idx) * height)
        stk.append((idx, h[i]))
                
    print(res)

거의 베낀 것 같긴 한데 다음에 문제 풀 때는 이렇게 풀 수 있게끔 하겠다.