[종만북] 울타리 - 스위핑 알고리즘

1.문제

문제요약 :

서로 높이가 다른 나무판자들로 이루어진 울타리가 있다. 이때 울타리에 포함되는 사각형 중 가장 넓이가 큰 사각형의 넓이를. 출력한다.
(단, 사각형의 밑변은 지면과 수평이다.)

 

입출력 :

시간복잡도:

기존의 분할정복 방법을 통해 O(NlgN)으로 문제해결하였다. 오늘은 스위핑알고리즘을 통해 O(N)으로 이 문제를 해결하고자 한다.
분할정복을 통한 문제 해결 알고리즘은 아래 링크를 참고.

 

[백준6549] 히스토그램에서 가장 큰 직사각형 - 분할정복

위 포스팅은 백준문제였지만 이 포스팅에서 다루는 종만북문제와 동일함

---

 

2. 문제 접근

MaxBox : 최대사각형

i번째 나무판자를 완전히 포함하고, i번째 나무판자의 길이를 높이로 갖는 사각형 중 가장 큰 사각형은 maxBox(i)라고 하자.
첫번째 나무판자부터 마지막 나무판자까지 maxBox(i)를 구한 후 그 중 가장 큰 값이 문제의 정답이 될 것이다.

index=2의 최대사각형(maxBox)

다음 그림에서 진한 사각형은 3번째 나무판자를 완전히 포함하고, 높이가 3번째 나무판자의 길이와 같으므로 진한 사각형의 넓이는 maxBox(3)일 것이다.

이때 max(i)값을 구하기 위해서 i번째 나무판자를 기준으로 좌우로 사각형을 넓혀갈때, 자신보다 낮은 나무판자를 만나게 되면 더 이상 넓힐 수 없고 maxBox(i)의 값이 결정된다.

위 그림을 보자 빨간색 나무판자를 기준으로 좌우로 사각형을 넓힌다. 이때 왼쪽은 2번째 사각형에서 멈추게 되고, 오른쪽은 8번째 사각형 전에 멈추게 된다. 이때 이 각각의 인덱스를 left, right라고 하자. 그러면 maxBox(i) = (right - left - 1) * height[i]가 된다. 이때 height[i]는 i번째 나무판자의 높이이다.

 

그렇다면 이 문제는 i번째 나무판자의 maxBox를 구할때 경계가 되는 left, right를 구하는 것이 핵심이 된다.

 

경계값(인덱스) (left, right) 구하기

 

경계값을 어떻게 구할까?

 

먼저 왼쪽(left)경계를 구해보자. left는 기준이 되는 나무판자에서 왼쪽으로 한칸씩 이동하면서 높이를 비교하여 구할 수 있다. 이때 처음으로 기준 나무판자보다 높이가 낮은 판자의 인덱스 값이 left가 된다.

 

left 를 구하기 위해서는 현재보다 왼쪽에 위치한 나무판자의 높이 정보가 필요하므로, 왼쪽에서 오른쪽으로 순회하면서 이전 정보들을 이용해 구할 수 있다.

 

스택을 이용해 이전 나무판자의 정보를 저장한다. 그 후, 왼쪽 판자부터 순회를 하면서 현재 나무판자보다 높은 나무판자를 모두 제거한다. 그러면 자연스럽게 현재 나무판자보다 낮은 나무판자만 스택에 남는다. 스택에는 현재 나무판자와 가까운 순서대로 저장되어 있으므로, 스택에 top에 위치한 인덱스 값이 left 값이 된다.

아래 코드는 모든 나무판자의 왼쪽 경계값(left)를 구하는 코드이다.

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// 0~n-1번째 판자의 높이가 순서대로 저장됨.
vector<int> fence;

// 0~n-1번째 판자의 왼쪽 경계 인덱스를 저장함.
vector<int> left;

void getLeft() {

    // 현재 나무판자보다 왼쪽에 위치한 나무판자의 정보를 저장
    stack<int> s;

    // 왼쪽부터 오른쪽으로 나무판자의 왼쪽 경계 값을 구한다.
    for (int i=0; i<fence.size(); ++i) {
        // 현재 나무판자보다 높은 나무판자는 스택에서 제거한다.
        // 스택에는 현재 나무판자보다 낮은 나무판자만 남게됨.
        while (!s.empty() && fence[s.top()] > fence[i]) s.pop();

        // 스택이 비어있으면 현재 나무판자보다 낮은 판자가 없는것이므로 경계 -1로 설정
        if (s.empty()) left[i] = -1;
        // 남아있는 나무판자 중 현재 나무판자와 가장 가까운 판자를 선택해서 
        // left값으로 설정
        else left[i] = s.top();

        // 현재 나무판자의 높이를 stack에 저장
        s.push(i);
    }
}

위 코드는 N개의 나무판자에 대해서 left 값을 구하므로 O(N)의 시간복잡도가 필요하다. 그리고 이때 while 문을 통해 이전의 값들을 검사하여 pop 연산을 시행하는데 이는 각 나무판자에 대해 최대 1번만 시행되므로 for문을 돌면서 반복되는 while문의 횟수는 최대 N번이다. 즉, 위 코드의 시간복잡도는 O(N)이다.

 

right를 구하는 것은 쉽지 않다. right로 left와 같은 관점으로 현재 나무판자의 오른쪽 으로 한칸씩 이동하면서 처음로 현재 나무판자보다 가까운 낮은 판자의 인덱스 값을 구하면 된다. 하지만 여기에는 가장 큰 문제가 있는데, left와 다르게 right는 오른쪽에 위치한 나무판자의 높이를 미리 알 수 없다는 것이다.

노란색 나무판자를 기준으로 오른쪽 값은 미리 알수 없다

위 그림을 보면 노란색 나무판자를 기준으로 순회를 하면서 현재 나무판자 기준, 왼쪽의 나무판자의 높이는 미리 알 수 있지만 오른쪽은 알 수 없다. 즉, right 값을 구하기 위해서는 추가적인 탐색이 필요한 것이다. 추가적인 탐색은 당여히 추가적인 시간복잡도를 요구한다. 즉, O(N)을 초과하는 시간이 요구 되는 것이다.

 

right 값이 정해지는 시점
right는 left와 다르게 순서대로 하나씩 구할 수 없다. 그렇다면 우리는 left 값을 구하는 과정에서 right값도 정해지지 않을까? 생각할 수 있다. 이전의 left 값을 구한느 코드를 구현하는 과정에서 스택에는 현재 나무판자보다 낮은 나무판자만 남아있다고 언급했다. 그림을 통해 보자.

노란색 막대는 stack에 들어간 막대고 빨간색 막대는 지워지는 막대다. 그림을 보면 현재 막대보다 높은 막대는 모두 지워지므로 나무판자의 높이가 오름차순으로 스택안에 정렬되는 것을 볼 수 있다. 즉, 스택에서 나보다 위에 있는 나무판자는 나보다 높은 것이다. 그렇다면 stack에서 pop이 되는 나무판자는 처음으로 자신보다 낮은 나무판자를 만났기 때문에 pop이 되는것이다. 즉, pop이 되는 시점에 각 나무판자의 right 값이 정해지는 것이다.

위 그림과 같이 나무판자가 stack에서 pop되는 시점에 그 나무판자를 pop시키는 나무판자의 인덱스값이 right로 결정된다. 이때 이 나무판자는 이미 left 값이 구해졌으므로 pop되는 시점에 최대사각형(maxBox)값을 구할 수 있다.

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// 0~n-1번째 판자의 높이가 순서대로 저장됨.
vector<int> fence;

// 0~n-1번째 판자의 왼쪽 경계 인덱스를 저장함.
vector<int> left;

int getMaxBox() {

    // 현재 나무판자보다 왼쪽에 위치한 나무판자의 정보를 저장
    stack<int> s;
    int ret = -1;

    // 왼쪽부터 오른쪽으로 나무판자의 왼쪽 경계 값을 구한다.
    for (int i=0; i<fence.size(); ++i) {
        // 현재 나무판자보다 높은 나무판자는 스택에서 제거한다.
        // 스택에는 현재 나무판자보다 낮은 나무판자만 남게됨.
        while (!s.empty() && fence[s.top()] > fence[i]) {
            // s.top() 인덱스의 나무판자는 right값이 i로 결정됨.
            int maxBox = (i - left[s.top()] - 1) * fence[s.top()];
            if (ret < maxBox) ret = maxBox;
            s.pop();

        // 스택이 비어있으면 현재 나무판자보다 낮은 판자가 없는것이므로 경계 -1로 설정
        if (s.empty()) left[i] = -1;
        // 남아있는 나무판자 중 현재 나무판자와 가장 가까운 판자를 선택해서 
        // left값으로 설정
        else left[i] = s.top();

        // 현재 나무판자의 높이를 stack에 저장
        s.push(i);
    }

    return ret;
}

이전의 left값을 구하는 과정에서 stack에서 현재보다 높은 나무판자를 pop할때 해당 나무판자의 right 값이 i(현재 나무판자의 인덱스)로 결정된다. 이때 maxBox값을 구하여 현재 최댓값보다 클 경우, 업데이트한다.

이를 모든 나무판자에 대해 수행하면 욽타리 문제를 해결할 수 있다.

 

이 코드는 기존의 left 값을 구하는 코드에서 while문 안에 O(1)으로 수행할 수 있는 maxBox 값을 구하는 과정이 추가된것뿐이므로 여전히 시간복잡도는 O(N)이다.

---

3. Solution

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

vector<int> fence;
vector<int> left;

int getMaxBox() {
    stack<int> s;
    int ret = -1;

    for (int i=0; i<fence.size(); ++i) {
        while (!s.empty() && fence[s.top()] > fence[i]) {
            int maxBox = (i - left[s.top()] - 1) * fence[s.top()];
            if (ret < maxBox) ret = maxBox;
            s.pop();
        if (s.empty()) left[i] = -1;
        else left[i] = s.top();

        s.push(i);
    }

    return ret;
}