오아시스 재결합 — 스택으로 한 번만 순회(O(n))

핵심 포인트

1. stack<pair<int,int>> 사용: (키, 같은 키의 연속 개수) 저장
2. 쌍의 개수 합은 커질 수 있으므로 ans는 long long
3. 시간 제한 1초 → 단 한 번 순회
4. 현재 사람의 키 h, 같은 키 개수 same 사용
5. 작은 키 제거: h보다 작은 키를 모두 pop 하며 개수 합산
6. 같은 키 묶음: 같은 키면 그 묶음의 크기를 ans에 더하고 합쳐서 push
7. 더 큰 사람 1명은 항상 보임: 스택이 비어있지 않다면 +1
8. 현재 사람을 (h, same+1)로 push
9. 위 과정을 반복

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000001];
stack<pair<int,int>> st; // {height, count of same heights}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int h = a[i];
        int same = 0;

        // 5) 작은 키 제거
        while (!st.empty() && st.top().first < h) {
            ans += st.top().second;
            st.pop();
        }

        // 6) 같은 키 묶음
        if (!st.empty() && st.top().first == h) {
            ans += st.top().second;       // 같은 키끼리는 서로 다 보임
            same = st.top().second;       // 묶음 크기 합치기
            st.pop();
        }

        // 7) 더 큰 사람 1명은 무조건 보임
        if (!st.empty()) ans++;

        // 8) 현재 사람 push (같은 키 묶음 + 1)
        st.push({h, same + 1});
    }

    cout << ans << '\n';
    return 0;
}

복잡도 & 주의점

• 시간복잡도: O(n) (각 원소는 스택에 한 번 push/pop)
• 공간복잡도: O(n)
• ans는 반드시 long long (쌍의 수가 최대 약 n²/2까지 커질 수 있음)