백준 17299 오등큰수 C++

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

17299번: 오등큰수

---

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

---

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

---

출력

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

---

해결방안 -> 수열의 등장횟수를 count라는 배열에 담아둔다.

그 후 수열의 끝부터 0번까지 for문 돌리면서 만약 스택이 비어있으면 스택에 수열의 값과 수열의 등장횟수를 넣어주고

벡터에 -1을 넣는다.

그리고 만약 수열의 등장횟수가 스택의 top에 있는 수열의 등장횟수보다 작다면 벡터에 탑에 있는 수열의 값을 넣어주고 스택에 {수열의 값,수열의 등장횟수}를 넣어준다.

그 이외의 경우에는 while문을 돌려서 스택을 pop해주는데 , while문 돌리면서 pop한 뒤 스택이 비어있거나 스택의 top에 있는 등장횟수가 수열의 등장횟수보다 크다면 while문을 빠져나온다.

while문이 끝나고 스택이 비어있으면 스택에 {수열의 값, 등장횟수}를 넣고 벡터에 -1을 넣는다.

만약 스택의 top에있는 등장횟수가 수열의 등장횟수보다 크다면 벡터에 {스택의 탑에 있는 수열의 값}을 넣어주고

스택에 {수열의 값,등장횟수}를 넣는다.

 

그 후 벡터를 뒤집어주면(algorithm 헤더의 reverse사용)된다.

---

전체 소스 코드->

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    stack <pair<int,int>> st;
    int arr[1100000];
    int count[1100000];
    vector<int> v;
    int n;
    cin >> n;
    for(int i = 0;i<n;i++){
        cin >> arr[i];
        count[arr[i]]++;
    }
 
    for(int i = n-1;i>=0;i--){
        if(st.empty()){
            st.push({arr[i],count[arr[i]]});
            v.push_back(-1);
        }
        else{
            if(count[arr[i]] < st.top().second){
                v.push_back(st.top().first);
                st.push({arr[i],count[arr[i]]});
            }
            else if(count[arr[i]] >= st.top().second){
                while(1){
                    if(st.empty() || st.top().second > count[arr[i]]){
                        break;
                    }
                    st.pop();
                }
                if(st.empty()){
                    v.push_back(-1);
                    st.push({arr[i],count[arr[i]]});
                }
                else if(st.top().second > count[arr[i]]){
                    v.push_back(st.top().first);
                    st.push({arr[i],count[arr[i]]});
                }
            }
 
        }
    }
    vector<int>::iterator iter;
    reverse(v.begin(),v.end());
    for(iter = v.begin();iter != v.end();iter++){
        cout << *iter << ' ';
    }
 
 
}