[백준 3015] 오아시스 재결합 C++

문제

백준 3015 오아시스 재결합

3015번: 오아시스 재결합

풀이

N = 500,000이므로 O(N^2)으로 푸는 것은 불가능하다.

따라서 Monotonic Stack을 활용한다.

Monotonic Stack

[알고리즘] Monotonic Stack

같은 값이 들어올 수 있으므로 해당 케이스만 추가로 처리해 주면 된다.

 

stack의 원소로는 (value, 연속하는 count)를 사용하였다.

현재 값보다 작은 값들을 모두 뺀 다음, 같은 값이 들어오면 다음과 같은 과정을 거친다.

1. stack을 pop 한다.

2. 같은 값끼리는 모두 볼 수 있다. 원래 stack에 있던 count만큼 VisibleCount를 증가시킨다.

3. stack에 남아 있는 원소가 있을 경우, 이들 중 첫 번째 원소 중에서도, 가장 뒤에 있는 친구만 새로 들어온 값을 볼 수 있다. 따라서 VisibleCount를 1 증가시켜 준다.

 

소스 코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int N = 0;
    cin >> N;
    // height, sameCount
    stack<pair<int, int>> st;
    long long visibleCount = 0;
 
    for (int idx = 0; idx < N; idx++)
    {
        int curHeight = 0;
        cin >> curHeight;
        
        // 현재 값보다 작은 값들 다 뺌
        while (!st.empty() && st.top().first < curHeight)
        {
            visibleCount += st.top().second;
            st.pop();
        }
 
        // 스택 제일 위값 비교
        // 비어있으면 그냥 push
        if (st.empty())
        {
            st.push({ curHeight, 1 });
        }
        // 같으면 계산
        else if (st.top().first == curHeight)
        {
            int tempCount = st.top().second;
            visibleCount += tempCount;
            st.pop();
            if (st.size() >= 1)
                visibleCount++;
 
            st.push({ curHeight, tempCount + 1});
        }
        // 작으면 그냥 push 및 카운트 증가
        else
        {
            st.push({ curHeight, 1 });
            visibleCount++;
        }
    }
 
    cout << visibleCount;
 
    return 0;
}