[BOJ. 3015] 오아시스 재결합

1. 링크 백준 3015 오아시스 재결합

2. 풀이

단순하게 Brute force로 푼다면 O(N²)이 걸리는 문제입니다.

하지만 stack을 이용하여 카운팅을 한다면 O(N)에 끝날 수 있는 문제입니다.

대략적인 카운팅을 하는 방법은 stack의 맨 위의 자료보다 작은 자료가 들어오는 경우 하나씩 카운트를 증가 시키며, stack의 맨 위의 자료보다 큰 자료가 들어올 경우, stack에 들어오는 자료보다 작은 값들을 하나씩 POP하면서 카운트를 증가시킬 것입니다.

하지만 stack 안에서 같은 키의 사람이 다른 사람이 여러명이 있을 경우에는 카운팅이 곤란해질 수 있으므로 다음과 같이 자료형을 선언합니다.
(height는 사람의 키, size는 같은 사람이 겹쳐있을 경우 합쳐진 사람의 수)

struct Person
{
    int height;
    int size;
};

case 1. stack이 비어있을 때

단순히 스택에 자료를 넣기만 하면 됩니다.

if (true == st.empty())
{
    st.push(people[i]);
    i++;
}

case 2. stack의 맨 위의 사람보다 키가 작은 사람이 들어올 경우

스택에 자료를 넣은 후 total을 하나 증가시킵니다.

if (st.top().height > people[i].height)
{
    total++;
    st.push(people[i]);
    i++;
}

case 3. stack의 맨 위의 사람과 키가 같은 사람이 들어올 경우

키가 같은 사람이 들어오는 경우에는 키가 같은 사람을 겹쳐서 하나처럼 계산을 할 것입니다. 그리고 스택안의 있는 사람이 겹쳐져 있을 경우, 키가 같은 사람만 서로 볼 수 있는 경우만 카운트해서 total에 더해준 다음, 스택에서 뽑아서 다음 Loop에서 다시 계산을 할 수 있도록 만들어줍니다.

else if (st.top().height == people[i].height)
{
    people[i].size += st.top().size;
    total += st.top().size;
    st.pop();
}

case 4. stack의 맨 위의 사람보다 키가 큰 사람이 들어올 경우

겹쳐 있는 사람 수 만큼 total에 더해주고, 스택의 원소를 빼줍니다. (들어오는 원소는 다음 loop에서 다시 계산된다)

else
{
    total += st.top().size;
    st.pop();
}

3. 코드

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct Person
{
    int height;
    int size;
};

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    vector<Person> people(N);
    for (int i = 0; i < N; i++)
    {
        cin >> people[i].height;
        people[i].size = 1;
    }
    
    stack<Person> st;
    long long total = 0;

    int i = 0;
    while (i < N)
    {
        if (true == st.empty())
        {
            st.push(people[i]);
            i++;
        }
        else
        {
            if (st.top().height > people[i].height)
            {
                total++;
                st.push(people[i]);
                i++;
            }
            else if (st.top().height == people[i].height)
            {
                people[i].size += st.top().size;
                total += st.top().size;
                st.pop();
            }
            else
            {
                total += st.top().size;
                st.pop();
            }
        }
    }
    cout << total << '\n';
}