오아시스 재결합

스택을 이용해서 간단히 풀 수 있다.

스택에 키를 넣으면서 만약 새로 들어온 키가 top보다 더 크면 어차피 top은 그 뒤의 사람을 볼 수 없기 때문에 제거하고, 

새로 들어온 키가 더 작을 때까지 이를 반복하고 새로 들어온 키를 push해주면 된다.

 

한가지 고려해야 할 점은 키가 같은 경우이다. 

키가 같으면 뒤의 사람까지 볼 수 있기 때문에 잘 처리해야 하는데, 이를 위해서 스택에 값을 넣을 때 pair로 넣어서 같은 키를 가진 사람이 몇명인지에 대한 정보를 추가로 전달해야 한다.

 

그래서 정리해보자면, 스택에 키를 넣으면서 top값과 비교하면 되는데

1. 키가 top보다 큰 경우 - top은 더 이상 뒤에 있는 사람들을 못 보기 때문에 top의 키를 가진 사람만큼 쌍을 더하고, pop을 하고 계속 진행

2. 키가 top보다 작은 경우 - 새로 들어온 키는 이제 top보다 앞에 있는 사람들을 볼 수 없기 때문에 쌍을 1 더하고, 스택에 새로 들어온 키를 push 해주고 break

3. 키가 같은 경우 - 키가 같은 사람끼리 서로 볼 수 있기 때문에 top의 키를 가진 사람만큼 쌍을 더하고 pop, 만약 스택이 아직 비지 않았다면 키가 같은 사람 말고 이전에 들어온, 키가 더 큰 사람도 새로 들어온 사람이 볼 수 있기 때문에 쌍을 하나 추가, 같았던 키를 가진 사람을 하나 추가해서 다시 push

while(!oasis.empty())
{
    pair<long long,int> a = oasis.top();
    if(a.first>x)
    {
        ans++;
        oasis.push(make_pair(x,1));
        break;
    }
    else if(a.first<x)
    {
        ans += a.second;
        oasis.pop();
    }
    else
    {
        ans += a.second;
        oasis.pop();
        if(!oasis.empty()) ans++;
        oasis.push(make_pair(x,a.second+1));
        break;
    }
}

과정을 요약한 핵심 코드이다.

#include<stdio.h>
#include<stack>
#include<algorithm>
using namespace std;
int N;
long long ans=0;
stack<pair<long long,int>> oasis;
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        long long x;
        scanf("%lld",&x);
        while(!oasis.empty())
        {
            pair<long long,int> a = oasis.top();
            if(a.first>x)
            {
                ans++;
                oasis.push(make_pair(x,1));
                break;
            }
            else if(a.first<x)
            {
                ans += a.second;
                oasis.pop();
            }
            else
            {
                ans += a.second;
                oasis.pop();
                if(!oasis.empty()) ans++;
                oasis.push(make_pair(x,a.second+1));
                break;
            }
        }
        if(oasis.empty()) oasis.push(make_pair(x,1));
    }
    printf("%lld",ans);
}

전체 코드이다.