백준 3015 오아시스

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

3015번: 오아시스 재결합

후기

먼가 짝을 짓는거 같긴해서 stack을 잠깐 생각은 했지만 아닌거 같아서 pass...

이런식으로 표를 그려서 2시간정도 이리저리 생각을 해보았지만 아이디어가 떠오르지를 않았습니다.

물론 떠오른 아이디어는 있었습니다. 이중 for문으로 돌리면 가능하지만

시간복잡도상 사람수가 50만이라 50 * 50만이 되면 절대 풀 수 없다고 생각해서 

- 구조체안에 이전 데이터를 넣어서 전달해야하나? 

- 현재까지의 최대값을 기준으로 이리저리 계산해야하나?

등등을 고민을 했지만 실패했습니다.

 

알고리즘이란 아이디어를 기반으로 시간복잡도를 줄여야하는데 아직 푼 문제수도 적다보니 아직은 아이디어가 쉽게 떠오르지는 않네요.

 

분석

해당 문제는 stack을 사용한 짝짓기 입니다.

브루트포스 안되기 때문에 그리디한 방법을 생각 해야됩니다.

경우는 크게 4가지 정도로 생각하면 될거 같습니다.

- 그냥 쭉 내려가는 경우 총 짝의 수는 n-1쌍

- 키가 싹다 같은 경우에는 (n-1) + (n-2) + (n-3) .... 쌍. 계속 같은게 나올 경우 "등차 수열"입니다. n * (n-1) / 2 

- 키가 점점 커지는 경우에는 n-1쌍

 

마지막 4번째 경우를 생각을 해보자면은 처음에는 내림 차순으로 내려가다가 갑자기 큰 키의 사람(A)이 나타났을 때, 이전 "(n-1) + 이전 사람의 수" 가 될 것입니다.

 

그리고 나서 빨간색 부분의 사람 부터는 A이전과 짝을 지을 수 없습니다. (아무리 키가 크더라도요)

 

그래서 일단 키가 "큰" 사람이 stack에 들어왔을 때 "무엇인가"를 해야 됩니다.

큰게 들어왔을 때 pop을 하는 식의 로직입니다.

문제가 좀 어렵기 때문에 "단계적"으로 구축을 하는게 좋습니다.

 

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

#define endl "\n"
#define ll long long
#define MAX 500004
ll n, ret, temp;
stack<ll> s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> temp;
        while (s.size() && s.top() < temp)
        {
            ret += 1;
            s.pop();
        }

        // 내림차순 일 경우 (아래의 if문 없다면 오름차순으로 구성된 경우만 count할 수 있습니다.)
        if (s.size()) ++ret; 
        s.push(temp);
    }
    cout << ret << endl;

    return 0;
}

위의 코드를 실행해보면

오름 차순일 때에도 잘 나오고 내림차순일 경우에도 잘 나옵니다.

하지만 위의 코드만으로는 같은 키의 사람이 계속입력받는 경우의 등차수열과 같이 계산되는 부분을 처리할 수 없습니다.

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

#define endl "\n"
#define ll long long
#define MAX 500004
ll n, ret, temp;
stack<pair<ll, ll>> s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        // ret 쌍의 수
        // stack의 first = 입력받은 수, stack의 second는 이전까지의 카운팅 된 같은 수의 개수
        cin >> temp;
        int cnt = 1;
        // stack의 size가 있고 stack의 top의 first(입력받은 수) 보다 현재 입력받은 수가 크거나 같다면
        while (s.size() && s.top().first <= temp)
        {
        	// 누적되어진 cnt값을 ret 쌍의 개수에 더해줍니다.
            ret += s.top().second;
            if (s.top().first == temp)
            {
                // 같은 값이 들어오면 이전의 cnt값에서 1을 더한 값을 cnt에 누적으로 더해준다.
                // while문이 끝나면 누적된 cnt는 stack에 들어갑니다.
                cnt = s.top().second + 1;
            }
            else cnt = 1;

            s.pop();
        }
        // 내림차순으로 계속 입력받을 경우를 위한 if문
        if (s.size()) ++ret;
        s.push({temp, cnt});
    }
    cout << ret << endl;

    return 0;
}

따라서 위의 코드와 같이 같은 키가 계속해서 입력을 받는 경우를 처리하기위해 cnt라는 변수를 두어 합을 누적하여 더할 수 있게 하는 로직이 필요합니다.

 

정리

2 2 2 8 4 5 10 이런식으로 키가 주어진다면 8이전으로 입력받는 부분은 생각할 필요도 없다라는 점과

stack에 들어가있는 것들 중에서 짝짓기만 생각하면 된다라는 점과

같은 값이 계속해서 입력을 받을 때 처리를 하는 부분이 핵심이 되겠습니다.