Java 17299 오등큰수

 

풀이 :

오큰수 문제와 유사하다. 오큰수는 자신의 오른 쪽에 있는 큰수를 찾는 것이었다면 오등큰수는 자신의 오른쪽에 자신의 등장횟수보다 큰 수를 찾는 것이다. 없으면 -1로 표시한다. 오큰수 문제에서 조건만 바꾸면 되는 것이라 간단하게 풀 수 있었다.

arr배열 : 수열을 저장한 int형 배열

cnt배열 : 수열에 있는 수가 등장한 횟수

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Stack<Integer> s = new Stack<>();
        int[] arr = new int[n];
        int[] cnt = new int[1000001];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            cnt[arr[i]] += 1;
        }
        for(int i = 0; i < n; i++){
            while(!s.isEmpty() && cnt[arr[s.peek()]] < cnt[arr[i]]){
                arr[s.pop()] = arr[i];
            }
            s.add(i);
        }
        while(!s.isEmpty()){
            arr[s.pop()] = -1;
        }
        for(int i = 0; i < arr.length; i++){
            sb.append(arr[i]).append(" ");
        }
        System.out.print(sb);
    }
}