[BOJ / c++] 3015 - 오아시스 재결합

링크

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

3015번: 오아시스 재결합

풀이

키가 같은 사람이 연속해서 줄을 설 경우를 생각하는데 오래 걸려서 많이 고민한 문제였습니다. 5555 (4C2) 65555 같은 경우만 생각해서 33332333 같은 경우를 고려하지 못했습니다.

스택에 차례대로 줄에 선 사람들을 넣으면서

1. top 보다 작으면 push를 하고

2. top 과 같으면 push 할 때 second를 top의 second += 1 (키가 같은 연속한 사람들의 수)

3. top보다 크면 top보다 작거나 같을 때 까지 pop

코드

#include <iostream>
#include <vector>
#include <stack>
#include <utility>
using namespace std;

stack<pair<int, int>> s;
vector<int> v;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        v.push_back(val);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && v[i] > s.top().first) {
            ans++;
            s.pop();
        }
        if (!s.empty() && v[i] == s.top().first) {
            s.push({v[i], s.top().second + 1});
            if (s.size() == s.top().second) ans += (s.top().second - 1); // 5555 같은 경우
            else if (s.size() > s.top().second) ans += s.top().second; // 6555 같은 경우
        }
        if (!s.empty() && v[i] < s.top().first) {
            ans++;
            s.push({v[i], 1});
        }
        if (s.empty()) s.push({v[i], 1});
    }
    cout << ans;
    return 0;
}