[Stack 활용] 17299. 오등큰수

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

17299번: 오등큰수

 

 

 

오큰수를 풀었다면 매우 쉽게 접근할 수 있는 문제입니다.

매커니즘은 동일한데, 오큰수와 달리 어떤 값을 비교하고 어떤 값을 정답 배열에 저장해야하는지만 잘 파악하면 쉽게 풀 수 있습니다.

 

우선 세팅을 하기 위해 배열을 입력받고 map을 이용해 카운팅하여 c 배열에 해당 숫자가 나온 횟수를 넣어줍니다.

 

오큰수에서는 배열 값을 스택에 넣고 스택의 탑값과 비교했다면, 오등큰수 배열을 만드는 과정에서는 비교 과정에서 v배열이 아닌 c 배열의 인덱스 값을 비교합니다. 물론 푸쉬할 때는 오큰수 배열과 동일하게 배열 값을 삽입합니다.

 

필자는 비교할 때는 stack의 top의 second ( c배열 ), 푸쉬할 때는 stack의 top의 first ( v배열 ) 사용하기 위해 스택에 v배열값과 c배열값을 pair로 묶어서 사용하였습니다. 

 

소스 코드 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <unordered_map>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n' 

using namespace std;

int n;
vector<int> v(1000001);
vector<int> cnt(1000001);
vector<int> ans(1000001,-1);
unordered_map<int, int> m;

stack<pair<int,int>> st;

int main()
{
    FASTio;
    cin >> n;

    for(int i=0;i<n;i++)
    {
        cin >> v[i];
        m[v[i]]++;
    }

    for(int i=0;i<n;i++)
    {
        cnt[i] = m[v[i]];
    }

    st.push(make_pair(v[n-1], cnt[n-1]));

    for(int i=n-2;i>=0;i--)
    {        
        while(!st.empty() && st.top().second <= cnt[i])
        {
            st.pop();
        }
    
        if(st.empty())
        {
            st.push(make_pair(v[i], cnt[i]));
            continue;
        } else {
            ans[i] = st.top().first;
            st.push(make_pair(v[i], cnt[i]));
        }
    }

    for(int i=0;i<n;i++){
        cout << ans[i] << ' ';
    }


    return 0;
}

 

 

처음에 시간초과가 발생해서 코드를 살펴보다가 map에서 시간초과가 걸린다는 것을 인지했습니다.
그래서 map을 unordered_map으로 바꿔서 해결.

 

참고자료 

hash_map | unordered_map | map 차이 비교, 특징 정리 - C++