[백준 17299] 오등큰수 (cpp, stack, array)

🚀  들어가며...

• 오른쪽에 존재하면서 등장횟수가, 현재 숫자보다 큰 수 중에서 가장 왼쪽에 있는 수가 오등큰수이다.
• 이 오등큰수를 출력하라.

• // 예시
  7
  입력 : 1 1 2 3 4 2 1
  
  등장횟수
  1:3
  2:2
  3:1
  4:1
  
  출력 : -1 -1 1 2 2 1 -1

 

🔗  문제

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

17299번: 오등큰수

 

📑  내용

입력배열과 정답배열을 따로 두었다.

그리고 입력의 갯수가 1,000,000개로 제한이 되어 있으며 그 범위도 1,000,000까지 이기 때문에

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

등장횟수 배열을 따로 선언하여 두었다.

    int *arr = new int[n+1]();      // 입력배열
    int *ans = new int[n+1]();      // 정답배열
    int *ngf = new int[1000001]();  // 등장횟수를 저장하는 배열

 

약간 복잡하지만

등장횟수 배열과 입력배열을 적절하게 사용하여, 마지막 인덱스부터 인덱스 0까지 검사해나가면

쉽게 풀린다.

 

 

💌 소스코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main(){
    int n;
    stack<int> st;

    cin >> n;

    int *arr = new int[n+1]();      // 입력배열
    int *ans = new int[n+1]();      // 정답배열
    int *ngf = new int[1000001]();  // 등장횟수를 저장하는 배열
    
    for(int i=1; i<=n; i++){
        int n;
        cin >> n;
        arr[i] = n;     // 입력배열
        ngf[n] += 1;    // 등장횟수 +1
    }

    // 우측에서부터 
    for(int i=n; i>=1; i--){
        // 현재 숫자의 등장횟수 >= 스택 top의 등장횟수
        // 스택 top의 숫자는 이제 필요없음 (pop)
        // 이 연산을 반복한다.
        while(!st.empty() && ngf[st.top()] <= ngf[arr[i]]){
            st.pop();
        }
        // 가장 우측의 정답배열은 -1이다.
        if(st.empty() || i==n){
            ans[i] = -1;
        }
        // 현재 숫자의 등장횟수 < 스택 top의 등장횟수
        // 정답배열에 넣어준다.
        else if(ngf[st.top()] > ngf[arr[i]]){
            ans[i] = st.top();
        }
        st.push(arr[i]);
    }

    for(int i=1; i<=n; i++)
        cout << ans[i] << ' ';

}