[백준] 17299 오등큰수 -Java

 

 

 

지난번에 풀었던 오큰수와 같은 로직으로 풀 수 있는 문제이다.

 

배열의 인덱스와 값을 가지는 스택 두 개를 선언하고 조건에 맞게 push와 pop을 진행해서 풀 수 있다.

 

오큰수 문제에서는 현재 탐색하는 원소보다 더 큰 수를 만나면 정답을 갱신했었는데, 이 문제에서는 원소들이 나온 횟수를 센 다음 현재 탐색하는 원소가 나온 횟수보다 더 많이 나온 횟수를 만났을 때 정답을 갱신해야 한다.

 

 

Java

 

 

import java.io.*;
import java.util.*;
 
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()," ");

		int[] ans = new int[N];
		int[] arr= new int[N];
		int[] arr_cnt = new int[1000001];

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

		Stack<Integer> stack = new Stack<>();
		Stack<Integer> stackidx = new Stack<>();

		for(int i=0; i<N; i++){
			while(stack.size() > 0 && arr_cnt[stack.peek()] < arr_cnt[arr[i]] ){
				ans[stackidx.peek()] = arr[i];
				stack.pop();
				stackidx.pop();
			}
			stack.push(arr[i]);
			stackidx.push(i);
		}


		while(stackidx.size() > 0){
			ans[stackidx.peek()] = -1;
			stackidx.pop();
		}


		ans[N-1] = -1;

	
		

		for(int i=0; i<N; i++){
			sb.append(ans[i]).append(" ");
		}
		System.out.println(sb);

	}
}