DevelopBeakjoon자료구조스택

백준 3015 - 오아시스 재결합

백준 3015 - 오아시스 재결합

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

문제 해설

입력되는 값이 총 50만개이다. 이 문제는 O(N) or O(NlogN)의 시간복잡도를 갖고 해결을 해야하는 문제이다.

  • 현재 값을 이전 값과 비교해가면서 문제를 해결 하는 방식이다.
  • 스택의 역할은 서로불 수 있는 값의 쌍을 저장하기 위한 역할을 한다.
  • 스택내의 값은 점점 작은 값이 추가 되야 한다.
  • 들어오는 값이 top보다 클 경우
    • 들어오는 값보다 큰 값이 나타날 때까지 pop을 진행하면서
    • pop을 진행할 때 해당 인원수 만큼 값을 더해준다.

같은 값이 들어올 경우을 어떻게 해결하는 것이 이 문제의 어려운 점이다.

  • 자료구조 pair를 이용한다.
  • first에는 사람의 키를 second에는 같은 키인 사람의 수를 저장한다.
  • 키가 같은 사람이 들어올 경우
    • 같은 키를 갖는 사람만큼 값을 추가해주고
    • 사람수를 + 1 해주고 해당 키를 다시 push해준다.

소스 코드

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

long long solution(vector<int> heights) {
    stack<pair<int, int>> st;
    long long result = 0;

    for (int heightsIndex = 0; heightsIndex < heights.size(); heightsIndex++) {
        int height = heights[heightsIndex];

        while (!st.empty() && height > st.top().first) {
            result += st.top().second;
            st.pop();
        }

        if (!st.empty()) {
            if (st.top().first == height) {
                pair<int, int> temp = st.top();
                st.pop();

                result += temp.second;
                if (!st.empty()) {
                    result += 1;
                }

                st.push({height, temp.second + 1});
            } else {
                result += 1;
                st.push({height, 1});
            }
        } else {
            st.push({height, 1});
        }
    }

    return result;
}

int main(void) {
    int numOfPeople;
    vector<int> heights;
    cin >> numOfPeople;

    for (int peopleIndex = 0; peopleIndex < numOfPeople; peopleIndex++) {
        int height;
        cin >> height;

        heights.push_back(height);
    }

    cout << solution(heights) << '\n';

    return 0;
}
Share