백준 3015 : 오아시스 재결합

문제 설명

---

N명의 사람들이 한 줄로 서 있고, 각 사람의 키가 주어진다. 서로 볼 수 있는 쌍은 두 사람 사이에 두 사람보다 키가 큰 사람이 없어야 한다. 이때 주어진 사람들중 서로 볼 수 있는 사람쌍의 총 수를 구한다.(1 ≤ N ≤ 500,000)

---

 

해당 문제는 스택을 통해 해결할 수 있다. 만약 키가 같은 사람이 주어지지않는다면, 모노톤 스택을 응용해 쉽게 해결이 가능하지만, 키가 같은 사람이 주어진다면 이를 따로 처리해야한다. 따라서 stack <pair<int, int>>를 잡은뒤, first = "키", second = "현재 키를 갖는 사람의 수" 로 정의하고 문제를 해결하면 된다.

 

 - 스택의 최상단 요소와 비교하여 현재 키 x보다 작은 키를 가진 사람들의 수를 ans(정답)에 더한다.

 - 현재 키가 스택의 최상단 키와 같으면, cnt를 갱신하고 ans에 (cnt - 1)을 추가한다. 스택이 1개 이상의 요소를 가지고 있으면 추가로ans를 증가시킨다.

 - 현재 키가 스택의 최상단 키보다 크거나 같으면 ans를 1 증가시킨다.

 - 스택에 현재 키와 그 키를 가진 사람 수를 저장한다.

 

---

소스 코드

#include <stdio.h>
#include <stack>

using namespace std;

int n;
long long ans;
stack <pair<int, int>> st;

int main()
{
    int i;
    scanf("%d", &n);
    for(i=0;i<n;i++) {
        int x;
        scanf("%d", &x);
        int cnt = 1;
        while(!st.empty()) {
            int t = st.top().first;
            if(t < x) {
                ans += st.top().second;
                st.pop();
            }
            else break;
        }
        if(!st.empty()) {
            int t = st.top().first;
            if(t == x) {
                cnt = st.top().second + 1;
                ans += (cnt - 1);
                if(st.size() > 1) ans++;
                st.pop();
            }
            else {
                ans++;
            }
        }
        st.push({x, cnt});
    }
    printf("%lld", ans);
    return 0;
}

 

 

자료형에 주의하자 ans는 int범위를 넘을 수 있다.