Algospot FENCE(시간복잡도:O(N))

문제 링크입니다: https://algospot.com/judge/problem/read/FENCE

http://jaimemin.tistory.com/310와 동일하지만 스택을 이용하여 시간 복잡도를 O(NlogN)->O(N)으로 단축시킨 코드입니다.

판자의 높이를 벡터에 저장한 다음에 마지막에 0을 넣어줍니다.(이렇게 하는 이유는 판자의 높이가 오름차순으로 저장되어있을 경우 width의 오른쪽 끝을 못 찾기 때문입니다.)

가장 왼쪽에 있는 울타리를 스택에 삽입하며 문제를 해결해가는데, 스택이 비어있거나 혹은 다음에 삽입하려는 울타리가 현재 스택 top에 있는 울타리보다 클 때는 넓이 비교를 하지 않고 바로 스택에 울타리를 push합니다.

다음에 삽입하려는 울타리가 현재 스택 top에 있는 울타리보다 작으면, top에 있는 막대 높이로 만들 수 있는 직사각형 가로 길이(width)의 오른쪽 끝이 됩니다.

#include <iostream>

#include <vector>

#include <stack>

#include <algorithm>

using namespace std;

 

int C, N;

vector<int> height;

 

//스택을 이용한 해법

int solveStack(void)

{

        //남아 있는 판자들의 위치

        stack<int> remaining;

        height.push_back(0); //제일 끝 울타리 높이가 i번째 울타리 높이보다 작아야 범위가 설정되므로

 

        int result = 0;

        for (int i = 0; i < height.size(); i++)

        {

                 //남아있는 판자들 중 오른쪽 끝 판자가 height[i]보다 높다면

                 //이 판자의 최대 사각형은 i에서 끝난다

                 while (!remaining.empty() && height[remaining.top()] >= height[i])

                 {

                         int j = remaining.top();

                         remaining.pop();

                         int width;

                         //j번째 판자 왼쪽에 판자가 하나도 안 남아있는 경우 left[j] = -1,

                         //아닌 경우 left[j] = 남아 있는 판자 중 가장 오른쪽에 있는 판자 번호

                         if (remaining.empty())

                                 width = i;

                         else

                                 width = (i - remaining.top() - 1);

                         result = max(result, height[j] * width);

                 }

                 remaining.push(i); //스택에 집어넣는다

        }

        return result;

}

 

int main(void)

{

        cin >> C;

 

        for (int i = 0; i < C; i++)

        {

                 height.clear();

                 cin >> N;

                 for (int j = 0; j < N; j++)

                 {

                         int h;

                         cin >> h;

                         height.push_back(h);

                 }

                 cout << solveStack() << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]