백준 17299 오등큰수 C++

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

17299번: 오등큰수

주어진 수열의 오른쪽에 있는 수 중 수열에 나온 횟수가 더 큰 가장 왼쪽의 수를 구하는 문제입니다.

예를 들어, 1,2,1,1,3,3,1 로 주어졌다면, 가장 오른쪽의 1보다 더 오른쪽의 수는 없으므로 -1, 그 다음 3은 2번 나왔지만, 오른쪽의 1은 4번 나왔으므로 1, 2의 경우 오른쪽의 1은 4번, 3은 2번 나왔지만, 2를 기준으로 1이 더 왼쪽에 있으므로 1이 정답입니다.

 

스택 2개를 이용해 스택에 {num, cnt} 와 같이 카운트된 횟수를 미리 다 계산한 스택을 만들고,

스택을 pop하면서 다음 스택이 비어 있으면 오등큰수가 없으므로 -1, 비어 있지 않다면 pop을 하면서 가장 먼저 카운트된 수가 더 큰 경우가 오등큰수입니다.

 

코드는 다음과 같습니다.

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

using namespace std;

int n;
vector<int> vec;
stack<pair<int, int>> stk1;
stack<pair<int, int>> stk2;
vector<int> result;

void init()
{
    cin >> n;
    int num;
    int cnt;
    int cnt_arr[1000001];
    memset(cnt_arr, 0, sizeof(cnt_arr));
    
    for(int i = 0; i < n; i++) {
        cin >> num;
        vec.push_back(num);
        cnt_arr[num]++;    
    }
    
    for(int i = 0; i < n; i++) {
        num = vec[i];
        cnt = cnt_arr[num];
        stk1.push({num, cnt});
    }
}

void calc()
{
    // 맨 마지막에 있는 애는 어짜피 -1이 정답
    pair<int,int> p = stk1.top();
    stk2.push(p);
    stk1.pop();
    result.push_back(-1);
    
    pair<int,int> p2;
    
    while(!stk1.empty()) {
        p = stk1.top();
        stk1.pop();
        
        // 스택2 비어 있는 경우 => 왼쪽에 만족하는 애 없음
        if(stk2.empty()) {
            result.push_back(-1);
            stk2.push(p);
            continue;
        }
        
        // 스택2에 있는 것 중 만족하는 애 나올 때까지 체크
        while(!stk2.empty()) {
            p2 = stk2.top();
            if(p2.second > p.second) {
                stk2.push(p);
                result.push_back(p2.first);
                break;
            }
            else {
                stk2.pop();
            }
        }
        
        // 스택2 다 돌아도 만족하는 것 없을 때
        if(stk2.empty()) {
            result.push_back(-1);
            stk2.push(p);
        }
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    calc();
    
    for(int i = result.size() - 1; i >= 0; i--) {
        cout << result[i] << ' ';
    }
}