[BOJ] 오아시스 재결합

오아시스 재결합

TimeLimit	MemoryLimit	Condition	TAG
1s	256MB	(1 ≤ N ≤ 500,000)	Stack

이 문제는 저번에 얘기했던 모노톤 스택을 좀 더 활용한 문제로 볼 수 있습니다.

저는 같은 값들을 가진 값들에 대해서 압축시키는 형식으로 처리를 했는데요. 더욱 모노톤 스택에 가깝게 풀이를 하려면 Binary search를 활용하는 방법도 가능할 것 같습니다.

단조성을 활용하다 보니 자연스럽게 정렬이 되구요. 이를 이용해서 이분 탐색을 돌릴 수 있고, 그러면 시간 안에 무조건 돌아가도록 만들 수 있습니다.

하튼 이문제도 여러 방법으로 풀 수 있기도 하고, 좋은 문제인 것 같습니다.

정답 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

vector<int> s;
vector<int> cnt;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll result = 0;
    
    int n;
    cin >> n;
    
    int current;
    while(n-->0){
        cin >> current;
        
        if(s.empty()){
            s.push_back(current);
            cnt.push_back(1);
            continue;
        }
        
        
        int p = 1;
        if(s.back() < current){
            
            while(!s.empty() && s.back() < current){
                s.pop_back();
                
                p+=cnt.back();
                cnt.pop_back();
            }
            p -= s.empty();
        }
        
        if(!s.empty() && s.back() == current){
            p+= cnt.back() - (cnt.size() == 1);
             
            cnt.back()++;
            s.pop_back();
        }else{
            cnt.push_back(1);
        }
        s.push_back(current);
        result += p;
        

    }

    cout << result;

    return 0;
}