[Python] 백준, 6549(스택)

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

6549번: 히스토그램에서 가장 큰 직사각형

풀어본 스택 문항 중에 가장 어려웠다. 고려해야할 조건도 너무 많았고, 약간의 구글링의 결과 분할정복이나 트리 쪽 문제라는 얘기도 있어서 추가적인 학습 후 돌아와야하나 고민하던 문제다.

 

계속 수정에 수정을 거듭하다보니 처음 의도했던 코드가 마구잡이로 더러워져서... 첫 접근 방법과 가장 스택다운 풀이를 소개하는 걸로 마무리 지으려한다.

 

 

첫 풀이의 방향

 1) 스택에 (높이, 가장 큰 넓이) push

 2) 스택의 가장 위의 값들의 높이와 현재 높이 비교 후 케이스 두개로 분류해 조건문 진행

 3) 직사각형의 넓이는 인접한 사각형의 넓이나 가장 작은 높이를 이용해 두가지를 동시에 고려하려함

 

이었는데, 넓이를 구하는게 너무 힘들었다. 경우가 다양해짐에 따라서 고정된 알고리즘이 있는 것 같지도 않았고, 생각한 경우를 뛰어넘는 경우들도 자꾸 등장해서 단순한 케이스 분류로는 해결하기 힘들다는 걸 깨달았다.

 

 

 

# PYTHON CODE 

import sys
 
while True:
    s = list(map(int, sys.stdin.readline().split()))
    s1 = s[0]
    if s1 == 0:
        break
    s2 = s[1:]
    stk = []
    answer = 0
 
    for i in range(s1):
        while stk and s2[stk[-1]] > s2[i]:
            k = stk.pop()
            if stk:
                width = i - stk[-1] - 1
            else:
                width = 1
            answer = max(answer, width * s2[k])
        stk.append(i)
 
    while stk:
        k = stk.pop()
        if stk:
            width = s1 - stk[-1] - 1
        else:
            width = s1
        answer = max(answer, width * s2[k])
    print(answer)

 

백준 저지에 업로드된 풀이들도 사실 다 비슷하다. 근데 직관적으로 이해하기엔 이 풀이가 가장 좋은 것 같다. 

 

이 문제의 초점은 높이가 작아지는 순간이다. 스택의 가장 밑에 존재하는 인덱스를 가장 작은 높이로 유지하면서, 스택에 쌓여있는 인덱스의 높이와 현재 인덱스의 높이를 비교하며 넓이를 계산한다.