[백준 JAVA] 17299번 풀이 - 오등큰수 (오큰수 유형)

package quiz;

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

/**
 * 오등큰수
 *
 **/
public class _17299 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int [] arr = new int[n];
        int [] cnt = new int[1000001];
        int [] result = new int[n];
        Stack<Integer> stack = new Stack<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            cnt[arr[i]]++;
        }

        for(int i=0; i<n; i++){
            while(!stack.isEmpty() && cnt[arr[stack.peek()]] < cnt[arr[i]] ){
                result[stack.pop()] = arr[i];
            }
            stack.add(i);
        }

        while (!stack.empty()){
            result[stack.pop()] = -1;
        }

        StringBuilder sb = new StringBuilder();
        for(int j : result){
            sb.append(j).append(" ");
        }
        System.out.println(sb);

    }
}

 

💬 참고 : 오큰수 (백준 17298번)

https://backshren20.tistory.com/664

[백준 JAVA] 17298번 풀이 - 오큰수 (인덱스 🥺..)

 

풀이

오큰수 보다 쉬운데.... 시간초과 때문에 버거웠다. 

cnt 배열을 어떻게 설정해야할지 헤매고 있었음 

-> 예전에 배열의 카운트를 구하는 문제를 풀 때도 n의 최대값 만큼 배열을 설정했는데, 이번 문제도 그렇게 풀었어야했다.