[정글 WEEK02_알고리즘] 개발 일지 - 문제 풀이

 

stack이 LIFO 구조라는건 표면적으로 알았지만 제대로 이해하지 못 하고 있었다. 

백준 17608_막대기, 2493_탑, 6549_히스토그램에서 가장 큰 직사각형 순으로 난이도를 높여가며 stack이 어떻게 쓰이는지 확실히 이해하게 되었다.   

 

17608_막대기와 2493_탑은 비교적 stack의 조건을 파악하기 쉬웠는데 6549_히스토그램은 코드를 보고도 이해하기 꽤 어려웠다. 그러다 그림을 그려보며 해결한 과정에 대해서 작성해보려고 한다. 

---

'6549_히스토그램에서 가장 큰 직사각형' 풀이

 

💡 핵심 아이디어

 막대기의 높이가 낮아질 때를 이전 막대들의 넓이를 계산할 타이밍으로 잡고 이전 막대의 길이를 높이로 해서 넓이를 계산하는 것이다. 너비는 조건에 따라 달라진다. 

 

 🤖 로직

 막대기들의 높이  heights가 [2, 1, 6, 5, 2, 3]이라고 할 때, heights의 마지막에 0을 추가하고 0 ~ len(heights) 까지의 범위를 순회한다. 0은 현재 막대 기준 이전 막대가 높았는지 기준으로 넓이를 계산할 것이기 때문에 계산을 위한 트리거로 추가한 값이며, stack에 있는 마지막 막대기 높이가 현재 막대기보다 크면 해당 막대기의 정리를 시작한다.

 

 높이는 heights[stack.pop()]으로 구하고, 너비는 stack이 비었을 때와 아닐 때로 나눠서 구한다. 

stack이 비었다는 것은 그 막대기가 현재 위치까지 전체 너비를 차지했던 막대기였음을 의미하고, stack이 남아있다면 아직 처리되지 않은 이전 막대들의 인덱스가 존재한다는 뜻이다.

 

 따라서 너비 = i if not stack else (i - 1) - (stack[-1] + 1 ) + 1이 되고, else 부분을 정리하면 너비 = i if not stack else i - stack[-1] -1 이 된다.

 

[2, 1, 6, 5, 2, 3, 0]에서는 아래 그림처럼 i=1, i=3, i=4, i=6에서 넓이를 구하게 되고, 이렇게 넓이를 구할 때마다 최대 넓이를 갱신한다.

 

모든 막대기를 순회하며 위 과정을 거친 후 만들어진 최대 넓이를 반환한다. 

 

 

코드는 아래와 같다.

def find_max_area(n: int, arr: list) -> int:
    stack = []
    max_area = 0
    arr.append(0) # 마지막 막대의 넓이까지 구하기 위한 트리거

    for i in range(n+1):
        while stack and arr[stack[-1]] > arr[i]:
            h = arr[stack.pop()]
            w = i if not stack else i - stack[-1] -1
            max_area = max(max_area, w * h)
        stack.append(i)
    return max_area

while True:
    line = input()
    if line == '0':
        break
    N, *heights = map(int, line.split())
    print(find_max_area(N, heights))