[Java][백준 17299: 오등큰수]

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

17299번: 오등큰수

 

Problem

크기가 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 이다.

 

Input 

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

 

Output

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

 

Insight

1. 오큰수 문제의 응용버전 => 아래 링크를 참고할 것 !  https://yu1moo.tistory.com/entry/Java%EB%B0%B1%EC%A4%80-17298-%EC%98%A4%ED%81%B0%EC%88%98?category=1012337 

[Java][백준 17298: 오큰수]

2. 자신의 오른쪽 숫자 중 빈도수가 자신보다 높으면서 가장 가까이 있는 수를 출력 

3. 빈도수를 저장하는 배열을 선언하여 input이 들어올 때마다 해당하는 숫자의 빈도수를 더해줌

4. 오큰수에서는 값을 비교하였다면, 오등큰수에서는 값에 해당하는 빈도수를 빈도수 배열에서 찾아 비교해줌

 

import java.util.*;
import java.io.*; 

public class Main {


    public static void main(String[] args) throws IOException{ 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        Stack<Integer> stack = new Stack<>(); 
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> result = new Stack<>(); 
        
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N]; 
        int freq[] = new int[1000001]; // 빈도수를 저장할 배열 선언 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        for(int i=0; i<N; i++){
            stack.add(Integer.parseInt(st.nextToken())); 
            freq[stack.peek()]+=1; 
        }
        
        for(int i=0; i<N ; i++){
            int k = stack.pop(); 
            int t = freq[k]; //빈도수 배열에서 해당 값의 빈도수를 찾음 
            while(!stack2.empty() && freq[stack2.peek()] <= t ){
                stack2.pop(); 
            }
            if (stack2.empty()){
                result.add(-1);
                stack2.push(k);  
            }
            else{
                result.add(stack2.peek());
                stack2.push(k); 
            }
        }
        while(!result.empty()){
            bw.write(String.valueOf(result.pop()));
        }
        
        bw.flush();
        bw.close(); 
    }
}