[백준] [C++] 3015번 오아시스 재결합 (stack)

 

1. 문제

3015번: 오아시스 재결합 (acmicpc.net)

3015번: 오아시스 재결합

 

2. 풀이

이 문제의 핵심은 같은 키를 가진 사람들이다.

 

문제의 정의에의해

같은 키를 가진 사람들이 연속적으로 줄을 서고 있을때

서로를 볼 수 있기 때문이다.

따라서 pair를 사용하여 같은 키인 사람의 수를 따로 저장하여 처리해야한다.

 

알고리즘은 다음과 같다

1) 앞에서부터 스택에 담는다

2) 스택에 담기전 스택의 top 보다 큰값이면 스택의 top이 더 큰값이 올때까지 pop해준다.

   pop의 의미는 현재 사람과, top의 사람이 쌍을 이룸을 의미한다.

3) 스택이 비어있지않으면, top과 현재 인덱스가 쌍을 이룬다는것을 의미한다.

    만약 top과 현재 인덱스의 키가 같으면 이는 top을 업데이트 시켜줘야함을 의미하며,

    현재의 인덱스는 이전의 연속적인 사람의 수들만큼 쌍이 생긴다는것을 의미한다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
int N;
vector<long long> h;
 
void solve() {
    long long answer = 0;
    vector<pair<long long, int>> s;
    for(int i = 0; i < N; i++) {
        int count = 1;
        while(!s.empty() && s.back().first < h[i]) {
            //h[i]와의 쌍
            answer += s.back().second;
            s.pop_back();
        }
        //s.back()과의 쌍
        if(!s.empty() && s.back().first == h[i]) {
            answer += s.back().second;
            count = s.back().second+1;
            s.pop_back();
        }
        if(!s.empty()) {
            answer++;
        }
        s.push_back({h[i], count});
    }
 
    cout<<answer;
}
void solve2() {
    long long answer = 0;
    vector<int> s;
    h.push_back(INT64_MAX);
    for(int i = 0; i < N+1; i++) {
        long long back = h[i], count = 0;
        if(i == N) {
            answer -= s.size();
        }
        while(!s.empty() && h[s.back()] < h[i]) {
            // 같은것끼리 쌍을 이루는것
            if(back == h[s.back()]) {
                count++;
                answer += count;
            }
            else {
                count = 0;
            }
            back = h[s.back()];
            //h[i] 와 쌍을 이루는것
            answer++;
            s.pop_back();
        }
        if(!s.empty() && h[s[0]] != h[i]) {
            //s[0] 와 쌍을 이루는것
            answer++;
        }
        s.push_back(i);
    }
 
    cout<<answer;
}
int main() {
    cin>>N;
    h = vector<long long>(N);
    for(int i = 0; i < N; i++) {
        cin>>h[i];
    }
    solve();
   // cout<<"\n";
   // solve2();
}