[백준] 201 - 자료구조 1 (연습) : 오등큰수 (17299번 JAVA)

[백준] 201 - 자료구조 1 (연습) : 오등큰수 (17299번 JAVA)

---

[풀이 방법]

* 중첩 for문은 절대 안됨 (시간 초과)

 

1. 수열 원소의 등장 빈도를 나타낸 배열을 생성

=> 등장 빈도 배열은 '1 ~ 1,000,000'의 인덱스를 가지는 크기여야 한다.

2. 등장 빈도 배열을 이용하여 비교 (비교 방법은 "오큰수" 때와 같음)

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Integer> stack = new Stack<>();
        
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

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

        // 등장 빈도 배열
        int[] fre = new int[1000001]; // 0 ~ 1000000
        for(int i=0; i<N; i++){
            fre[arr[i]] ++;
        }

        for(int i=0; i<N; i++){

            // 비교 기준 : 각 수별 등장 빈도
            while(!stack.isEmpty() && fre[arr[i]] > fre[arr[stack.peek()]]){
                arr[stack.pop()] = arr[i];
            }

            stack.push(i);
        }

        while(!stack.isEmpty()){
            arr[stack.pop()] = -1;
        }


        for(int i=0; i<N; i++){
            bw.write(arr[i] + " ");
        }

        bw.flush();
        bw.close();
    }
}