[Algorithm] 백준 - 6549번 히스토그램에서 가장 큰 직사각형 (Swift)

문제 소개

난이도가 어려워질수록 문제 자체는 간단해지는 느낌이 든다. 히스토그램이 주어지고 넓이가 가장 큰 직사각형을 구하는 프로그램을 작성하는 문제이다.

문제 풀이

나는 스택을 활용하여 풀었다. 아래와 같은 히스토그램이 있다고 생각해보자.

아래와 같이 stack의 마지막 요소의 높이가 추가하려는 높이보다 작다면 stack에 append해준다.

마지막은 이제 4번째 인덱스가 3번째 인덱스의 높이 4보다 낮은 상황이다. 이제 이 상황에서 로직을 사용하게 된다. 넣으려는 요소의 -1을 하면 앞에 쌓인 블록들의 width가 나온다. 이것을 현재 블록의 높이, 블록의 인덱스의 차이를 이용하여 넓이의 최댓값을 갱신해준다. 만약 pop하고 마지막 값이 없다면 그냥 width를 곱해주면 된다.

pop하는 값의 높이가 추가하려는 높이보다 낮을때까지 이를 반복해서 진행한 후 이렇게 다시 stack에 append해주면 된다.

5번째 블록의 높이가 1이기 때문에 위에서 진행한 방법을 다시 적용한다.

마지막에 stack이 비어있지 않다면 위에서 했던 것을 그대로 해준다.

음... 잘 설명이 되었는지 모르겠다. 처음엔 아리송 할 수 있지만 어떤 방식으로 구하는지 이해해보고 코드를 작성하다보면 이해가 잘 갈 것이라고 믿는다. 👾

정답 코드

import Foundation

while let input = readLine(), input != "0" {
    var nh = input.split(separator: " ").map { Int($0)! }
    let n = nh[0]
    var stack: [(index: Int, height: Int)] = []
    var ans = 0
    
    func update(_ i: Int) {
        /// 스택의 마지막 높이가 추가하려는 높이 이상이라면
        while let popped = stack.last, popped.height >= nh[i] {
            stack.removeLast()
            /// pop하고나서 마지막 인덱스까지가 width가 됨
            if let last = stack.last {
                ans = max(ans, popped.height * (i - 1 - last.index))
            } else {
                /// stack이 비어있다면 인덱스 자체가 width가 됨
                ans = max(ans, popped.height * (i - 1))
            }
        }
    }
    
    for i in 1...n {
        update(i)
        stack.append((i, nh[i]))
    }
    
    /// 함수의 재사용을 위한 추가 작업
    /// 마지막에 0을 추가해줘서 nh[n+1]를 0으로 만들어 무조건 stack을 비워줌
    nh += [0]
    update(n+1)
    
    print(ans)
}