알고스팟 문제 풀이 FENCE

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "FENCE"에 대한 풀이입니다.

목차

1. 문제 해결 전략 - 무작정 풀기
2. 코드 전문 - 무작정 풀기
3. 문제 해결 전략 - 분할 정복
4. 코드 전문 - 분할 정복

FENCE 문제 URL은 다음과 같습니다.

• FENCE 문제

문제 해결 전략 - 무작정 풀기

먼저, 이 문제를 풀기 위해서 "무작정 풀기" 전략을 선택해 봅시다. 제일 쉬운 방법은 모든 인덱스를 돌면서, 그 높이를 가진 울타리 영역의 최대치를 구하면 됩니다. 무슨 소리냐면, 첫 번째 입력을 예로 살펴봅시다.

이런 울타리에서 첫 번째 판자의 높이로 울타리를 잘라낸다고 하면, 오른쪽 판자의 높이가 자신보다 낮습니다.따라서 다음 영역의 울타리를 잘라낼 수 있습니다. 영역의 너비는 7(7 * 1)이 됩니다.

두 번째 판자의 높이로 울타리를 잘라낸다면, 높이가 제일 낮기 때문에, 해당 높이로 처음부터 끝까지 울타리를 잘라낼 수 있습니다. 영역의 너비는 7(1 * 7)입니다.

이제 세 번째 판자의 높이로 잘라내봅시다. 먼저 바로 왼쪽의 높이가 자신보다 낮습니다. 또한 오른쪽으로 +4 에 위치한 판자가 자신의 높이보다 작기 때문에, 다음 영역을 잘라낼 수 있습니다. 영역의 너비는 20(5 * 4)입니다.

이런 식으로 인덱스를 돌면서, 구할 수 있는 최대 영역을 구하면 됩니다. 이를 코드로 표현하면 다음과 같습니다.

 

int solution(const int N, const vector<int>& heights) {
    
    int result = 0;

    for (int i=0; i<N; i++) {
        int height = heights[i];
        int right = i + 1, left = i - 1;

        while (right < N && heights[right] >= height) {
            right += 1;
        }

        while (left >= 0 && heights[left] >= height){
            left -= 1;
        }
        
        int width = right - left - 1;
        result = max(result, height * width);
    }

    return result;
}

 

코드 전문 - 무작정 풀기

다음은 무작정 풀기를 적용한 알고리즘 풀이 코드 전문입니다. 위에서 설명하지 않은 main 함수에서 문제의 입력을 다루고 있으니 유의해서 봐주세요!

 

int solution(const int N, const vector<int>& heights) {
    
    int result = 0;

    for (int i=0; i<N; i++) {
        int height = heights[i];
        int right = i + 1, left = i - 1;

        while (right < N && heights[right] >= height) {
            right += 1;
        }

        while (left >= 0 && heights[left] >= height){
            left -= 1;
        }
        
        int width = right - left - 1;
        result = max(result, height * width);
    }

    return result;
} 

int main() {
    int C;
    cin >> C;

    if ( !(0 < C && C <= 50) ) {
        cout << "fail: C must be between 1 and 50" << endl;
        return 0;
    }

    for (int i=0; i<C; i++) {
        int N;
        cin >> N;

        if ( !(1 <= N && N <= 20000) ) {
            cout << "fail: N must be between 1 and 20000" << endl;
            return 0;
        }   

        vector<int> heights = vector<int>(N, 0);

        for (int j=0; j<N; j++) {
            int h;
            cin >> h;

            if ( !(0 <= h && h <= 10000) ) {
                cout << "fail: h must be between 1 and 10000" << endl;
                return 0;
            }   

            heights[j] = h;
        }

        int result = solution(N, heights);
        cout << result << endl;
    }

    return 0;
}

 

알고리즘을 제출하면 800ms로 통과하고 있습니다. 그러나, 우리 문제의 최대 입력은 20,000이고, 시간 제한은 3000ms입니다. 이 알고리즘의 시간 복잡도는 O(N ^ 2)이기 때문에, 최대 입력을 넣었을 때는 통과하지 못할 것입니다. (400,000,000 > 3,000,000)

문제 해결 전략 - 분할 정복

저는 이 알고리즘을 최적화하기 위해서 "분할 정복" 패러다임을 적용할 것입니다. 이 문제는 다음의 3가지로 분할 할 수 있습니다.

 

첫 번째, 가장 큰 직사각형이 왼쪽 부분에 존재할 때

두 번째, 가장 큰 직사각형이 오른쪽 부분에 존재할 때

세 번째, 가장 큰 직상각형은 왼쪽과 오른쪽 부분에 걸쳐 있을 때

1, 2의 경우 반으로 나누어 부분 문제를 재귀 호출하여 해결할 수 있습니다.

 

int solve(const vector<int>& heights, int left, int right) {
    //...

    // 반으로 나누고,
    int mid = (left + right) / 2;
    // 부분 문제 해결
    int ret = max(solve(heights, left, mid), solve(heights, mid + 1 ,right));

    //...
}

 

이제 문제는 양쪽에 걸쳐 있을 때를 해결하는 것입니다. 양쪽에 있을 때는 어떻게 해결할 수 있을까요? 먼저 가운데 mid를 기준으로 잘라낼 영역을 선택합니다. (mid, mid+1)

이 때, mid+1의 높이가 적기 때문에, 영역의 너비는 다음과 같아집니다.

 

2 * mid+1의 높이 = 2 * 6 = 12

 

그렇게 시작해서, 왼쪽 오른쪽으로 서서히 영역을 넓혀나가면 됩니다. 다음과 같이 동작하게 되지요. 먼저, 오른쪽으로 영역이 넓혀집니다. 너비는 12에서 18로 변합니다.

이제 왼쪽으로 영역을 한칸 더 넓힙니다. 이때 최소 높이는 6에서 5로 갱신되고 최대 너비도 20으로 갱신됩니다.

또 오른쪽으로 한 칸 더 영역을 넓힙니다. 이 때 최소 높이는 3으로 변하지만, 최대 너비는 갱신되지 않습니다. (20 > 15)

이제 왼쪽으로 한 칸 더 영역을 넓힙니다. 이 때 최소 높이는 1로 변하지만, 최대 너비는 갱신되지 않습니다. (20 > 6)

이제 왼쪽으로 한 칸 더 영역을 넓힙니다. 이 때 최소 높이는 1로 유지되고, 최대 너비 역시 갱신되지 않습니다. (20 > 7)

어떻게 동작하는지 아시겠나요? 아래 과정을 반복해서 가운데에 영역에 최대치를 구하면 됩니다. 이것은 다음과 같이 표현할 수 있습니다.

 

1. lo = mid, hi = mid+1 부터 시작합니다.
2. 영역 중 최소 높이를 구합니다. (height = min(heights[lo], heights[hi]))
3. 영역을 구합니다. (area = 2 * height)
4. left < lo || hi < right를 만족할 때까지 다음을 반복합니다.
   1. hi < right && (lo == left || heights[lo - 1] < heights[hi + 1]) 을 만족한다면 다음을 실행합니다.
      1. hi를 오른쪽으로 한 칸 옮깁니다.
      2. 최소 높이를 갱신합니다. (height = min(height, heights[hi]))
   2. 아니라면 다음을 실행합니다.
      1. lo를 왼쪽으로 한 칸 옮깁니다.
      2. 최소 높이를 갱신합니다. (height = min(height, heights[lo]))
   3. 영역을 구해서, 최대치를 갱신합니다.

이제, 여기서 구한 최대 영역과, 왼쪽에서 최대와 오른쪽에서 최대를 비교한 것과 비교해서 최댓값을 구하면 됩니다. 코드는 다음과 같습니다.

 

int solve(const vector<int>& heights, int left, int right) {
    //...
    //중간에 결쳐있을 때,
    int lo = mid, hi = mid + 1;
    int height = min(heights[lo], heights[hi]);
    int area = height * 2;

    while (left < lo || hi < right) {

        if (hi < right && (lo == left || heights[lo - 1] < heights[hi + 1])) {
            hi += 1;
            height = min(height, heights[hi]);
        } else {
            lo -= 1;
            height = min(height, heights[lo]);
        }   
        
        area = max(area, height * (hi - lo + 1));
    }

    return max(ret, area);
}

 

그리고 이렇게 했을 때, 예외 상황을 적용해주어야 합니다. 그래야 재귀 호출에서 벗어날 수 있을테니까요. 이 문제에서 예외 상황은 left, right가 같을 때, 즉 한 판자만을 가리킬 때입니다. 이 때는 판자의 높이를 그대로 반환하면 됩니다. 왜냐하면, 다음 그림처럼 너비는 1이니까요.

코드는 다음과 같습니다.

 

int solve(const vector<int>& heights, int left, int right) {
    if (left == right) {
        return heights[left];
    }

    //...
}

 

그래서 이 문제를 해결하기 위한 전체 코드는 다음과 같습니다.

 

int solve(const vector<int>& heights, int left, int right) {
    if (left == right) {
        return heights[left];
    }

    int mid = (left + right) / 2;
    int ret = max(solve(heights, left, mid), solve(heights, mid + 1 ,right));

    int lo = mid, hi = mid + 1;
    int height = min(heights[lo], heights[hi]);
    int area = height * 2;

    while (left < lo || hi < right) {

        if (hi < right && (lo == left || heights[lo - 1] < heights[hi + 1])) {
            hi += 1;
            height = min(height, heights[hi]);
        } else {
            lo -= 1;
            height = min(height, heights[lo]);
        }   
        
        area = max(area, height * (hi - lo + 1));
    }

    return max(ret, area);
}

int solution(const int N, const vector<int>& heights) {
    return solve(heights, 0, N-1);    
} 

 

solution 함수에서 분할 정복이 적용된 solve 함수를 부르고 있습니다. 이는 "무작정 풀기"때 만든 입력, 즉 main 함수 변경 없이 그대로 사용하기 위해서 만들어진 패턴입니다. 유의깊게 살펴봐주세요.

코드 전문 - 분할 정복

"분할 정복" 패러다임을 적용한 코드 전문입니다. main은 이전과 같습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int solve(const vector<int>& heights, int left, int right) {
    if (left == right) {
        return heights[left];
    }

    int mid = (left + right) / 2;
    int ret = max(solve(heights, left, mid), solve(heights, mid + 1 ,right));

    int lo = mid, hi = mid + 1;
    int height = min(heights[lo], heights[hi]);
    int area = height * 2;

    while (left < lo || hi < right) {

        if (hi < right && (lo == left || heights[lo - 1] < heights[hi + 1])) {
            hi += 1;
            height = min(height, heights[hi]);
        } else {
            lo -= 1;
            height = min(height, heights[lo]);
        }   
        
        area = max(area, height * (hi - lo + 1));
    }

    return max(ret, area);
}

int solution(const int N, const vector<int>& heights) {
    return solve(heights, 0, N-1);    
} 

int main() {
    // 무작정 풀기와 동일
}

 

이 알고리즘을 제출하면 300ms 이내로 문제를 해결하는 것을 알 수 있습니다. 분할정복을 적용해서 알고리즘 복잡도를 O(N * log(N))으로 낮췄기 때문에, 최대 입력을 넣어도 약 290,000 (= 290ms < 3,000ms) 정도로 문제를 해결할 수 있기 때문입니다.