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;
}