[백준/Baekjoon] 3015 오아시스 재결합 C++ :: Data Structure

https://www.acmicpc.net/problem/3015

3015번: 오아시스 재결합

---

1. Logic

1. pair<int, int>를 원소로 가지는 stack 하나를 선언한다. pair는 <키, 같은 키를 가진 사람 수>이다.

2. 현재 입력받은 키보다 작은 애들은 무조건 볼 수 있기 때문에 pairCnt를 올려주고 어짜피 나보다 작은애들이기 때문에 나보다 큰 애가 들어오게 되면 내 뒤의 작은애는 보지 못하기때문에 스택에서 pop해주고 다시 넣어주지 않는다. > 이 방식으로  스택을 항상 내림차순으로 정렬해준다.

3. 만약 스택에서 만난 TOP값과 현재 입력받은 값이 같을 경우 pairCnt에 같은 키를 가진 사람 수를 나타내는 stack.top().second를 더해주고 sameHeightCnt에도 더해준다.

4. 이번에 입력받은 키와 같은 키를 가진 사람의 수를 pair로 묶어서 넣어준다. 

 

2번까지 하게 되면 Stack에 남아있는 키의 경우의 수는 stack.top().first==height / stack.top().first > height 이렇게 2가지 경우의 수가 밖에 나올 수 없다.

1번 stack.top().first==height인 경우에는 키가 같을 경우 다 볼 수 있기 때문에 top().second값인 같은 키를 가진 사람의 수를 pairCnt에 더해주고 sameHeightCnt에 +1을 해서 다시 stack에 push해주면 된다.

2번 stack.top().first > height인 경우 나보다 큰 사람이 2개가 있다. 내 시점에서는 키 큰 사람 둘 다 볼 수 있지만 가장 키가 큰 사람 시점에서 보면 2번재로 키 큰 사람에게 막혀 내가 보이지 않기 때문에 pairCnt를 하나만 올려주고 현재 키와 sameHeightCnt를 stack에 push해준다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n;

stack<pair<int, int>> sta;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;
    
    long long pairCnt = 0;
    
    for(int i = 0; i < n; i++) {
        int height;
        cin >> height;
        
        int sameHeightCnt = 1;
        
        while(!sta.empty() && sta.top().first < height) {
            pairCnt += sta.top().second;
            sta.pop();
        }
        
        if(!sta.empty()) {
            if(sta.top().first == height) {
                pairCnt += sta.top().second;
                sameHeightCnt += sta.top().second;
                
                if(sta.size() > 1) pairCnt++;
                
                sta.pop();
            }
            else {
                pairCnt++;
            }
        }
        sta.push({height, sameHeightCnt});
    }
    
    cout << pairCnt;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐