[Algorithm] 백준 6549 히스토그램에서 가장 큰 직사각형 - node.js

이 글은 백준 6549 히스토그램에서 가장 큰 직사각형 문제를 풀이한다. 코드는 javascript로 작성되었다.

문제

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다.

예제 입력 1

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

출력

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

8
4000

풀이

접근

무식하게 풀 수 있을까?

문제를 풀 수 있는 가장 간단한 방법은 2중 for문으로 가능한 모든 l과 r을 순회하며 위 값을 계산하는 것이다. 그런데 이 문제에서 직사각형의 최대 수는 100,000이므로 O(n^2)시간이 걸리는 이 알고리즘으로 해결할 수 없다.

알고리즘

분할 정복

분할 정복 알고리즘을 만들기 위해서 문제를 어떻게 분할할지 가장 먼저 정해야 하는데, n개의 판자를 절반으로 나누어 두 개의 부분 문제를 만들면 우리가 찾는 최대 직사각형은 다음 세 가지 중 하나에 속한다.

• 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낼 수 있다.
• 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낼 수 있다.
• 가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.

이때 첫 번째와 두 번째 경우는 반으로 나눈 부분 문제를 재귀 호출하여 해결할 수 있다. 세 번째 경우의 답을 빠르게 구할 수 있으면 이 중 가장 큰 직사각형을 선택하면 된다.

양쪽 부분 문제에 걸친 경우

이 경우 직사각형은 반드시 부분 문제 경계에 있는 두 직사각형을 포함한다. 이 직사각형에서 시작해 사각형을 가로로 한 칸씩 더 높은 판자를 포함하게끔 확장해야 한다. 가장 큰 직사각형을 찾으려면 항상 사각형의 높이를 최대화하는 방향으로 확장해야 한다.

구현

코드

const input = [];

const strToNumArr = (str) => str.split(" ").map((numString) => Number(numString));

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", function (line) {
    input.push(line.trim());
  })
  .on("close", function () {
      //맨 마지막 0 삭제
      const N = input.length;
      input.splice(N-1, 1);

      input.forEach((inputStr)=>{
        const [len, ...heightList] = strToNumArr(inputStr);
        const result = getResult(heightList, 0, len-1);
        console.log(result);
      })
  });

//[left, right] 구간에서 찾아낼 수 있는 가장 큰 직사각형의 넓이를 반환
const getResult = (heightList, left, right) => {
    //기저 사례: 직사각형이 하나밖에 없는 경우
    if(left===right){
        return heightList[left];
    }

    //[left, mid], [mid+1, right]의 두 구간으로 문제를 분할
    const mid = Math.floor((left+right)/2);
    //양쪽 부분 문제를 재귀호출 후 더 큰 직사각형의 넓이를 저장
    let result = Math.max(getResult(heightList, left, mid), getResult(heightList, mid+1, right));
    //두 부분에 모두 걸쳐있는 사각형 중 가장 큰 것 탐색
    let low = mid, high = mid+1;
    let height = Math.min(heightList[low], heightList[high]);
    //[mid, mid+1]만 포함하는 너비 2인 사각형을 고려
    result = Math.max(result, height*2);

    //사각형이 입력 전체를 덮을 때까지 확장
    while(low>left || high<right){
        //항상 높이가 더 높은 쪽으로 확장
        if(high<right && (low===left || heightList[low-1]<heightList[high+1])){
            high++;
            height = Math.min(height, heightList[high]);
        } else{
            low--;
            height = Math.min(height, heightList[low]);
        }
        //확장 후 사각형의 넓이
        result = Math.max(result, height*(high-low+1));
    }
    return result;
};

시간 복잡도

위 코드는 주어진 n 크기의 배열을 n/2 크기의 배열 두 개로 나눈 뒤 이들을 각각 해결한다. 이 과정의 시간 복잡도는 O(logn)이다.

재귀호출 외에 함수 내에서 하는 일은 두 부분에 걸쳐 있는 사각형을 찾는 작업이 있는데, 이 과정에서 너비가 2인 사각형에서 시작해 너비가 n인 사각형까지 하나하나 검사하므로 시간 복잡도는 O(n)이다.

따라서 이 알고리즘의 시간 복잡도는 O(nlogn)이다.