[백준 6198] 옥상 정원 꾸미기

옥상 정원 꾸미기

문제설명

빌딩의 수를 입력 받고, 각 빌딩의 높이를 입력 받은 뒤, 총 관리인이 옥상정원을 확인할 수 있는 수를 출력한다.
이 때 빌딩은 오른쪽으로만 확인 가능하고, 오른쪽의 빌딩의 높이가 같거나 높으면 더이상 빌딩을 확인할 수 없다.

알고리즘

1. 입력 값들을 입력 받는다
2. stack을 확인하여 비었는지, 현재 top의 크기가 새로 넣으려는 크기보다 같거나 작은지 판단한다.
3. top의 크기가 같거나 작은 경우 오른쪽으로 볼 수 없는 경우를 의미하니까 pop하여 제거해준다.
4. 새로운 값을 stack 에 넣는다.
5. stack의 크기 -1만큼 정답에 더해준다.

시간초과난 코드 -> 벡터로만 풀었을 때

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;


int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    vector <int> v;
    cin >> N;
    while (N)
    {
        int h;
        cin >> h;
        v.push_back(h);
        N--;
    }

    int cnt = 0;
    for (int i = 0; i < v.size()-1; i++)
    {
        int temp = v[i];
        for (int j = i+1; j < v.size(); j++)
        {
            if (temp > v[j])
                cnt++;
            else
                break;
        }
    }
    cout << cnt << "\n";
    return 0;
}

정답

#include <stdio.h>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;


int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector <int> v (N);//총 크기만큼 초기화
    stack <int> s;

    for (auto &x : v)//값 저장
        cin >> x;

    long cnt = 0;
    for (int i = 0; i < v.size(); i++)
    {
        while (!s.empty() && s.top() <= v[i])//현재 넣을려고 하는 값이 맨위의 값보다 크면->stack에 있는것이 그 뒤에것을 볼 수 없으므로
            s.pop();//제거
        s.push(v[i]);//새로운 값넣기 
        cnt += s.size() - 1;//크기 추가
    }
    cout << cnt << "\n";
    return 0;
}

고찰

시간복잡도로 인해서 이중 for문으로 단순 조회하면 시간이 초과된다.
따라서 stack 구조를 이용해서 문제를 해결해야한다.
monotone stack이라는 알고리즘으로 아래를 기준으로 내림차순이 유지되도록 만들어서 문제를 해결한다.