6549번: 히스토그램에서 가장 큰 직사각형 / platinum 5 / 스택, 구현

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

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

 

처음 짠 코드 : 시간초과(python) / 메모리초과(pypy)

'''
6549번: 히스토그램에서 가장 큰 직사각형 / platinum 5 / 
'''
import sys

sys.setrecursionlimit(10**8)
input = sys.stdin.readline


def find_left(value, left, count):
    global cnt
    if left <= 0 or info[left] < value:
        cnt += count
    else:
        find_left(value, left - 1, count + 1)


def find_right(value, right, count):
    global cnt
    if right >= len(info) or info[right] < value:
        cnt += count
    else:
        find_right(value, right + 1, count + 1)


while True:
    # 입력 받기
    info = list(map(int, input().split()))
    # 종료 조건
    if info[0] == 0:
        break
    # 가장 큰 직사각형 구하기
    # index 자리 높이 기준 사각형 만들기
    big_square = info[0]
    for index in range(1, len(info)):
        cnt = 1
        find_left(info[index], index - 1, 0)
        find_right(info[index], index + 1, 0)
        area = cnt * info[index]
        if big_square < area:
            big_square = area
    print(big_square)

 

정답 코드

'''
6549번: 히스토그램에서 가장 큰 직사각형 / platinum 5 / 스택, 구현
'''
import sys

input = sys.stdin.readline

while True:
    # 입력 받기
    info = list(map(int, input().split()))
    n = info.pop(0)
    # 종료 조건
    if n == 0:
        break
    # 가장 큰 직사각형 구하기
    stack = []
    big_area = 0
    for i in range(n):
        while len(stack) != 0 and info[stack[-1]] > info[i]:
            index = stack.pop()
            if len(stack) == 0:
                width = i
            else:
                width = i - stack[-1] - 1
            area = width * info[index]
            big_area = max(big_area, area)
        stack.append(i)
    # 스택에 남아있는 부분
    while len(stack) != 0:
        index = stack.pop()
        if len(stack) == 0:
            width = n
        else:
            width = n - stack[-1] - 1
        area = width * info[index]
        big_area = max(big_area, area)
    print(big_area)

 

스택을 활용

 

해당 문제는 스택에 어떤 위치의 녀석들이 차근차근 쌓이는지 이해하는 것이 중요!

 

왼쪽부터 오른쪽으로 높이를 하나씩 체크 하기

- 현재 위치 i 의 높이랑 , 최근에 스택에 저장된 stack[-1]위치의 높이랑 비교해서,

- i 위치의 높이가 더 크면 스택에 저장

- i 위치의 높이보다 작은 녀석들을 pop 해서 넓이 구하기