[파이썬] 백준 6549 : 히스토그램에서 가장 큰 직사각형 (플레5)

[파이썬] 백준 6549 : 히스토그램에서 가장 큰 직사각형 (플레5)

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

---

풀이

방향성 생각

• 사실 문제를 보면 딱 봐도 세그트리 문제임을 대충 알 수 있다.
• 할 줄 몰라서 모노톤 스택 / 유니온 파인드로 풀이.
• 모노톤 스택같은 경우는, 배열을 순회하면서 이전에 가지고 있던 정보들을 기억해야한다는 점에서 떠올릴 수 있다.
  • 첫 번째는 인덱스, 두 번째는 이전 높이를 기억해야한다.
  • 이를 위해서, 스택에 튜플 형태로 넣어주기
• 유니온 파인드의 경우는 큰 막대부터 점점 병합을 진행한다.
  • 작은 막대부터 병합하는 경우, 큰 막대와 결합하는 과정에서 그룹의 최소 높이가 잘못 갱신되는 문제가 발생한다.
  • 따라서, 큰 막대순으로 나오게 정렬을 진행하고, 인접 그룹들과 유니온 파인드를 진행한다.

 

---

전체코드

import sys
input = sys.stdin.readline

while True:

    cmd,*arr = list(map(int,input().split()))

    if cmd == 0:
        break

    stack = []
    answer = 0
    # 이전 저장했던 값들이 현재 값보다 클 경우 제거한다. 제거하면서 높이 갱신해주기
    for e,val in enumerate(arr + [0]):
        s = e
        while stack and val < stack[-1][1]:
            s,h = stack.pop()
            w = e-s
            answer = max(answer,h*w)
        stack.append((s,val))
    print(answer)

 

---

import sys
input = sys.stdin.readline

def find(x):
    if P[x] != x:
        P[x] = find(P[x])
    return P[x]

inside = lambda x : 0<=x<N
INF = float('inf')

while True:

    N, *arr = list(map(int,input().split()))

    if not N:
        break

    # 각 분리 집합에 저장할 정보들
    P = [i for i in range(N)]
    selects = [False]*N
    width = [0]*N
    min_height = [INF]*N

    answer = 0
    # 큰 막대부터 나오도록 정렬하기 (작은 쪽으로 정렬하면 항상 그룹의 최소 높이로 비교해버려서 4,5에서 8이 나오는 대신 전체 밑변 7*1이 답으로 나온다)
    for x,h in sorted([(x,h) for x,h in enumerate(arr)], key = lambda x : -x[1]):

        # 높이가 없는 경우는 패스
        if not h:
            continue

        # 사용 유무 select / 그룹의 최소 높이 min_height / 그룹 밑변 길이 width
        selects[x] = True
        min_height[x] = h
        width[x] = 1

        # 현재 x와 인접한 x+1, x-1의 부모를 기준으로 병합을 진행한다
        px = find(x)
        for y in [x+1,x-1]:
            if inside(y) and selects[y]:
                py = find(y)

                # 부모가 다른 경우 작은 쪽으로 루트를 몰아주고, 그룹의 길이와 최소 높이를 지정한다.
                if px != py:
                    P[max(px,py)] = min(px,py)
                    width[min(px,py)] += width[max(px,py)]
                    min_height[min(px, py)] = min(min_height[px], min_height[py])

        # 높이 갱신하기
        w,min_h = width[px], min_height[px]
        answer = max(answer,h,w*min_h)

    print(answer)

• 스택이 들어왔을 때,

코멘트

• 슬슬 세그트리를 배워야 할 때가 왔다...