[Cpp] 백준 3015번 오아시스 재결합

문제를 딱보는 순간

monotonic stack으로 풀어야겠다! 생각이 들었습니다.

다만 monotonic stack은 중복된 엘리멘트 요소가 존재할 경우에는 정확한 연산이 안나오는 문제가 있으므로

해당 포인트를 어떻게 해결하는가가 관건이고

 

마지막으로!!! 결과값은 int형 정수의 범위보다 클 수 있다...

 

int returnCountMonotonicStack(vector<int>& vec)
{
    if(vec.empty() || vec.size() == 1) return 0;
    
    stack<pair<int, int>> monotonicStack;

    long cnt = 0;

    for(int i = 0; i < static_cast<int>(vec.size()); i++)
    {
        while(!monotonicStack.empty() && monotonicStack.top().first < vec[i])
        {
            cnt += monotonicStack.top().second;
            monotonicStack.pop();
        }

        if(monotonicStack.empty())
        {
            monotonicStack.emplace(vec[i], 1); //무조건 마주치는 쌍은 1쌍은 존재하기 때문에
        }
        else
        {
            //같은 크기의 쌍이 존재하는 경우에는 마주치는 쌍이 2개가 존재하게 된다.
            //그러므로 중복을 제거해주고 카운트를 증가시켜준다. (monotonic stack은 중복 엘리멘트가 있음 정확한 값이 안나옴)
            if(monotonicStack.top().first == vec[i])
            {
                pair<int, int> top = monotonicStack.top();
                monotonicStack.pop();

                cnt += top.second;

                if(!monotonicStack.empty())
                {
                    cnt++;
                }

                top.second++;
                monotonicStack.emplace(top);
            }
            else // 작은 경우에는 무조건 마주치는 쌍이 1개가 존재한다.
            {
                monotonicStack.emplace(vec[i], 1);
                cnt++;
            }
        }
        
    }

    cout<<cnt<<endl;

    return cnt;
}

int main()
{
    int n; //기다리고 있는 사람의 수
    cin >> n;

    vector<int> v(n);
    
    for(int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    returnCountMonotonicStack(v);
	
    return 0;
}
#pragma endregion