백준: 오아시스 재결합

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

[1.문제이해]

이문제의 경우 최대 N=500,000 이고 시간제한은 1초이내 이므로
nlogn이하의 시간복잡도를 보여야한다.이분탐색으로 접근하기도 힘들다. 한번의 풀스캐닝(O(N)) 작업에 있어서 현재 지점까지 읽은 메타정보를 기반으로 memorization을 해야한다. 예를 들어서 생각 해보자.

각 index의 순번에서 왼쪽방향으로 최대한 볼 수 있는 갯수의 합을 구하면된다.

다음의 경우 크게 세가지 경우가 있다.

1번

케이스 3->4, 4->5, 7->8 이 있다.
4번index 지점에서는 0~3번 index의 모든 필요로 하다.
5번index 지점에서는 4,0 index의 정보를 필요로 하다.
8번index 지점에서는 7,6,5 index의 정보가 필요로 하다.

즉 자신의 왼쪽까지의 index수들증 자신보다 큰수가 나오기 전까지의 index들중 단조감소하는 수열들의 정보를 가지고 있으면 된다.

2번

케이스: 6->7 이 있다.
4번index 지점에서는 5~6번 index의 모든 필요로 하다.
결론은 위 1번과 마찬가지이다.

3번

케이스: 0->1, 1->2, 2->3, 5->6이 있다.
2번index 지점에서는 1번index의 정보를 필요로 한다.
3번index 지점에서는 2번index의 정보를 필요로 한다.
6번index 지점에서는 5번index의 정보를 필요로 한다.

즉 이러한 경우일때는 바로 왼쪽의 정보만을 가지고 읽을 수 있다.

결론

왼쪽 지점을 기준으로 가지고 있어야 하는 메타 정보는 단조 감소하는 수열의 정보이다. 이때 단조 감소하는 수열의 정보를 읽고 나면(1->4 번의 경우이다.) 그다음부터 자신보다 작았던 단조 수열의 정보는 쓰이지 않는다.( 5번 이후부터는 1->3으로 이루어지는 단조 감소수열은 쓰이지 않는다.)

[2.알고리즘]

다음을 바탕으로 해결방법을 세워 보면 다음과 같다.
Stack을 기반으로 구현해보면 다음과 같다. stack은 단조 감소 수열의 정보를 담고 있다. 즉 stack은 내림차순으로 정렬 되어 있다.

1번의 경우:

현재 Stack의 수중 현재 나온 수 보다 작은 값들을 전부 비워준다. 이과정에서 count++한다. 그리고 현재 지점을 넣어준다.

3번의 경우:

stack에 쌓고 count++한다.

2번의 경우:

똑같은 수를 또 stack에 넣을 필요없이 해당 수가 여러개 있다는것을 표시하면된다. 즉 stack에 들어가는 parameter는 <수,갯수>가 되겠다.

[3.구현]

#include <bits/stdc++.h>
#define ll long long
#define val first
#define num second
using namespace std;
int N;
ll cnt = 0;
stack<pair<ll, ll>> st; //firsts 값 second같은값의 갯수
//4 3 2 1
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        pair<ll, ll> cur;
        cin >> cur.val;
        cur.num = 1;
        while (!st.empty() && st.top().first < cur.val) //현재 나온값이 이전값보다 클경우 7 4 3 2 1 5
        {
            cnt += st.top().num;
            st.pop();
        }
        if (!st.empty() && st.top().first == cur.val) //현재 나온값이 이전값이랑 같을경우
        {
            cnt += st.top().second;
            cur.num = ++st.top().second;
            st.pop();
        }
        if (!st.empty() && st.top().first > cur.val) //현재 나온값이 이전값보다 작을경우 5 4 3 2
            cnt++;
        st.push(cur);
    }
    cout << cnt;
    return 0;
}