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

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

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

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

🤔 문제분석

이틀공안 고민하다가, 결국 해결하지 못하여, 풀이법을 참조하였습니다. 😂

해당 문제를 해결하는 방법은 스택을 활용하여 푸는 방법과, 분할정복, 세그먼트 트리를 활용하여 푸는 방법이 있습니다.

분할정복, 세그먼트 트리

최소 높이를 찾아서, 그 지점을 기준으로 양쪽을 분할한다. 해당 구간에서 최대 넓이는 지점을 기준으로, 왼쪽에 있거나, 오른쪽에 있거나, 걸쳐있다.

여기서 최소 길이를 빠르기 찾기위하여 세그먼트 트리를 활용한다.

스택

입력받은 값을 순회 하면서 스택으로 현재 만들 수 있는 가장 큰 직사각형 넓이를 계속 계산한다.

현재스택에서 자기자신보다 작은 값이 왔을경우

• 이전에 존재했던 스택들을 모두 pop 하고, 최대 넓이를 갱신
• 현재값을 push

현재스택에서 자기자신보다 큰 값이 왔을경우

• 최대 넓이를 갱신하지 않고, 현재 값을 push

현재스택에서 자기자신보다 작은 값이 왔을경우 지금까지 만들 수 있는 모든 직사각형의 넓이를 구하여 최대 넓이 값이 반영해야한다. 그림으로 표현하면 아래와 같다.

빨간색 : 스택에서의 꼭대기의 값보다 작은값이 왓을경우 넓이를 갱신해준다.

초록색 : 마지막에 0을 넣음으로, 마지막에 모든 스택을 pop 시켜, 넓이의 값을 갱신시킨다.

📝 의사코드

세그먼트 트리

1. 세그먼트 트리를 초기화한다.
2. 분할정복
   1. 세그먼트 트리를 활용하여 최소 높이를 구한다. 3가지중 최소값을 선택한다.
      1. 최소 높이의 인덱스를 기준으로 왼쪽 값
      2. 최소 높이의 인덱스를 기준으로 오른쪽 값
      3. 최소 높이의 * 현재 길이의 값

스택

1. 데이터를 순회하면서 스택이 존재하면, 스택의 마지막값과 비교한다.
   1. 스택의 값보다 작은경우는 모든 스택을 pop 시키면서 넓이를 구한다.
   2. 넓이를 구하는방법
      1. 너비 : 스택이 존재한다면, i - stack[-1] -1 그렇지 않다면 i
      2. 높이 : stack에서 pop한 값

💻 코드

세그먼트 트리, 분할정복

import sys
input = sys.stdin.readline
INF = int(1e9) + 1
sys.setrecursionlimit(int(1e5))

def merge(left, right):
    if left[0] > right[0]:
        return right
    else:
        return left

def init(start, end, node):
    if start == end:
        tree[node][0] = temp[start]
        tree[node][1] = start
        return tree[node]
    else:
        mid = (start + end) // 2
        l_init = init(start, mid, node*2)
        r_init = init(mid + 1, end, node*2+1)
        tree[node] = merge(l_init, r_init)
        return tree[node]
    
def query(start, end, node, left, right):
    if left > end or right < start:
        return [INF, 0]
    
    if start >= left and end <= right:
        return tree[node]
    
    mid = ( start + end ) // 2
    l_min = query(start, mid, node * 2, left, right)
    r_min = query(mid + 1, end, node * 2 + 1, left, right)
    return merge(l_min, r_min)
    
def solve(start, end):
    if start == end:
        return temp[start]
    if start > end:
        return -1
    
    height, idx = query(0, arr_size-1, 1, start, end)
    
    a = solve(start, idx - 1)
    b = solve(idx + 1, end)
    c = height * ((end - start) + 1)
    return max(a, b, c)
        
while True:
    temp = list(map(int, input().split()))
    arr_size = temp.pop(0)
    if arr_size == 0:
        break
    
    tree_size = arr_size * 4
    tree = [[0,0] for _ in range(tree_size)]
    init(0, arr_size-1, 1)
    print(solve(0, arr_size-1))

스택

import sys
input = sys.stdin.readline

while True:
    data = list(map(int, input().split()))
    if data.pop(0) == 0:
        break
    
    data.append(0) # 마지막 모든 데이터를 pop시키기 위해서 추가함.
    
    stack = []
    max_ans = 0
    
    for i in range(len(data)):
        while stack and data[stack[-1]] > data[i]:
            idx = stack.pop()
            
            if not stack:
                width = i
            else:
                width = i - stack[-1] - 1
            
            max_ans = max(max_ans, width * data[idx])
            
        stack.append(i)
        
    print(max_ans)

🎯 피드백 및 개선사항

두가지의 문제 풀이 방식으로 여러 방식으로 접근하여, 문제 해결 사고력이 증진 되었습니다.

다음에 스택문제나 세그먼트 트리 활용 문제를 풀때, 어떤식으로 접근해야할지 다시한번 더 생각해보게 되었습니다.

❓다른사람은 어떻게 풀었을까

문제 풀이를 시간내에 하지못하여 다른 사람의 문제 풀이를 참고하였습니다.