[백준 17299] 오등큰수 - 자바

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

17299번: 오등큰수

---

1. 풀이

문제를 보면 [백준 17298] 오큰수 - 자바  와 비슷한 것을 볼 수 있다.

'오큰수'문제에서는 사용자가 입력한 숫자를 기준으로 비교를 했다면, 이번 문제는 사용자가 입력한 숫자의 빈도를 가지고 비교를 한다.

'오큰수'문제를 정확히 이해했다면, 이 문제도 금방 풀 수 있다. ( 난 쉽지 않았다... )

여러모로 복습이 필요한 문제이다.

---

2. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new 	OutputStreamWriter(System.out));
		
		// 배열의 입력
		int num = Integer.parseInt(bf.readLine());
		String[] input = bf.readLine().split(" ");
		
		// 결과값을 넣을 배열
		int[] result = new int[num];
		
		// 입력된 숫자를 담는 배열
		int[] nums = new int[num];
		for(int i = 0; i < num; i++)
			nums[i] = Integer.parseInt(input[i]);
		
		// 숫자들의 등장한 횟수를 담는 배열
		int[] nums_count = new int[1000001];
		for(int i = 0; i < num; i++)
			nums_count[nums[i]]+=1;
		
		// 인덱스 담을 Stack
		Stack<Integer> stack = new Stack<Integer>();
		
		for(int i = 0; i < num; i++) {
			if(stack.isEmpty())
				stack.push(i);
			while(!stack.isEmpty() && nums_count[nums[stack.peek()]] < nums_count[nums[i]]) {
				result[stack.pop()] = nums[i];
			}
			stack.push(i);
		}
		
		while(!stack.isEmpty())
			result[stack.pop()] = -1;
		
		for(int i = 0; i < num; i++)
			bw.write(result[i]+" ");
		bw.flush();
		return;
	}
}