[Python 3] BOJ - 6549 "히스토그램에서 가장 큰 직사각형"

  # 문제 링크 : https://www.acmicpc.net/problem/6549

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

 

 # 풀이 : 

 이 문제는 분할 정복과 스택으로 풀 수 있는데, 이번 포스팅에서는 스택으로 설명하겠다. 스택의 중요한 특성은 항상 가장 최상단에 존재하는 값이 의미가 없다면 pop을 해주는 것이다. 과연 이 문제에서 스택의 성질이 유효할까? 결론적으로는 그렇다. 

<그림 1. 높이가 바뀌는 경우>

 현재 높이 2짜리인 Now번째 직사각형이 스택에 있다고 가정하자. 그런데 높이 1짜리인 Next번째 직사각형이 존재한다면, 높이가 2짜리인 Now번째 직사각형은 높이가 맞지 않으므로 너비를 확장시킬 수 없다. 그러나, 높이가 1짜리인 Next번째 직사각형은 높이가 더 낮기 때문에 너비를 확장시킬 수 있다. 결국 Now번째 사각형은 더 이상 너비를 확장할 수 없으므로 의미가 없어지게 된다. 따라서 스택의 pop을 통해 스택에서 제외시킨다. 반대로 Next번째 직사각형은 앞으로 올 직사각형의 높이에 의해 너비가 현재보다도 더 넓어질 가능성이 있으므로, 즉 유의하므로 스택에 push하는 것이다.

 그렇다면, 현재 높이와 인덱스를 비교하면 최대 높이를 구할 수 있을까? 결론적으로는 그렇지 않다. 아래의 예를 보자

<그림 2. 인덱스 변화에 따른 반례>

 만일 스택에 (현재 높이, 현재 인덱스)로 저장하게 되면 그림 2와 같은 반례에 올바른 정답을 나타낼 수 없다. 왜냐하면 Next의 높이가 1이기 때문에, Now를 pop한 후, Now의 높이 * (Next idx - Now idx) = 2가되는데, 실제 정답은 4이다. 이렇게 오차가 나타나게 되는 원인은 스택이 오름차순으로 구성되어 있기 때문이다. 이전 사이클로 돌아가보자. 인덱스 0인 직사각형은 인덱스 1번 직사각형이 높이가 더 작으므로 스택에서 pop되었을 것이다. 그런데, 인덱스 1 직사각형은 빠져나간 인덱스 0까지 확장할 수 있으므로, 이전에 pop한 인덱스를 저장하였다가 pop이 중지되는 순간의 인덱스를 스택에 저장해야 한다. 즉, 높이가 4인 0번째 직사각형을 pop하고 높이가 2인 1번째 직사각형을 push할때, (2, 1)이 아니라 (2, 0)이 들어가야 위와 같은 반례를 올바로 처리할 수 있다.

 그런데 또 고려해야하는 것이 있다. for문을 순회해도 스택이 반드시 비어있다는 보장이 없다는 것이다. 그림 1에서는 높이가 1짜리 직사각형 2개와 높이가 3짜리 직사각형 2개가 최종적으로 스택에 남아있다. 이 경우 이미 너비의 확장을 다 고려한 경우이므로 계속 pop을 하면서 최대값과 인덱스를 빼주고 높이를 곱해준 값이 정답이 된다. 따라서 이 모든 결과의 최대값을 갱신하면 정답을 올바로 구할 수 있다. 

 

 # 코드

import sys

# st : 스택, ans : 정답배열
st = []
ans = []
while True:
    info = list(map(int, sys.stdin.readline().split()))
    if info[0] == 0:
        break
    total = info[0]
    info = info[1:]
    temp = []
    for i in range(len(info)):
        # cut : 꺼낸 직사각형의 인덱스 저장
        cut = i
        # 스택이 비어있지 않고 top의 높이보다 지금 직사각형의 높이가 더 작다면
        while st and st[-1][0] > info[i]:
            # 스택에서 pop
            height, idx = st.pop()
            # 높이 저장
            temp.append(height * (i - idx))
            # 확장되는 인덱스 갱신
            cut = idx
        # 처리 후 스택에 저장
        st.append((info[i], cut))
    # 끝까지 순회하고도 스택이 비지 않았다면
    while st:
        height, idx = st.pop()
       	높이 저장
        temp.append(height * (total - idx))
    # 높이 저장 중 가장 큰 값을 정답배열에 저장
    ans.append(max(temp))
    
# 정답 출력
for i in ans:
    print(i)