백준 3015번 오아시스 재결합

🔒문제 url

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

🔑알고리즘

stack에 {키,키가 같은 사람의 수}를 pair<int,int>으로 저장한다.

• 현재 사람이 stack의 top보다 큰 경우
  • stack.top().second만큼 쌍이 추가된다.
  • 다음 사람부터는 더이상 이전 사람을 볼 수 없으므로,
    top 원소를 stack에서 제거한다.
  • 현재 사람을 push한다.
• 현재 사람이 stack의 top과 같은 경우
  • 최종적으로 키가 같은 사람의 수를 1 증가시켜야하는 상황이다.
  • stack의 top 원소를 제거한 후, stack이 비어있다면 (키가 같은 사람의 수)만큼, 비어있지 않다면 (키가 같은 사람의 수 + 1)만큼 쌍이 추가된다.
  • stack에 키가 같은 사람의 수를 갱신하여 push한다.
• 현재 사람이 stack의 top보다 작은 경우
  • 한 쌍만 추가된다.
  • stack에 push한다.
• stack이 비어있는 경우
  • stack에 push한다.

🪄전체 코드

#include <iostream>
#include <stack>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);

int n;

void INPUT()
{
    IAMFAST
    cin >> n;
}

void solution()
{
    long long ans = 0;

    stack<pair<int,int>> st;
    while(n--)
    {
        int h; cin >> h;

        while(!st.empty() && st.top().first < h)
            ans += st.top().second,
            st.pop();

        if(st.empty()) st.emplace(h,1);
        else
        {
            if(st.top().first == h)
            {
                int cnt = st.top().second;
                st.pop();

                ans += (!st.empty()) ? cnt+1 : cnt;
                st.emplace(h,cnt+1);
            }
            else
            {
                ans++;
                st.emplace(h,1);
            }
        }
    }
    cout << ans;
}

int main()
{
    INPUT();
    solution();
}

🥇문제 후기

간단한 문제, 까다로운 구현.