[BOJ 17299] 오등큰수 (java)

문제 링크 https://www.acmicpc.net/problem/17299

문제풀이

package basics_200;

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

public class BOJ17299 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		Stack<Integer> stack = new Stack<Integer>();
		int n = Integer.parseInt(br.readLine());
		//입력받은 배열 
		int[] array = new int[n];
		//해당 숫자 빈도수 배열 
		//! 사이즈 100001 안해주면 ArrayIndexOutOfBounds 남 ! 
		int[] count = new int[1000001];
		//오등큰수 담길 배열 
		int[] result = new int[n];

		//한줄 입력받은거에서 숫자 하나씩 잘라 배열에 저장 
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}

		// 각 숫자들의 빈도수를 계산해서 해당 인덱스에 넣어줌 
		for (int i = 0; i < array.length; i++) {
			count[array[i]]++;
		}
		
		//맨 처음 인덱스를 먼저 넣어주고
		stack.push(0);
		
		//for문을 돌면서 오른쪽 수가 오등큰수인지 아닌지 비교 
		for (int j = 1; j < array.length; j++) {
			// 스택 맨 위의 인덱스에 해당하는 빈도수 보다 옆에 있는 수의 빈도수가 더 크다면 -> 오른쪽 애가 오등큰수이므로
			while (!stack.isEmpty() && count[array[stack.peek()]]<count[array[j]]) {
				//오등큰수 배열에 찾은 오등큰수를 넣어줌 
				result[stack.peek()] = array[j];
				//해당 인덱스는 오등큰수를 찾았으니까 스택에서 pop
				stack.pop();
			}
			//오등큰수가 아니라면 스택에 푸시 
			stack.push(j);
		}
		
		//for문을 전부 다 돌고 나서도 오등큰수를 못찾은 애들을 pop하면
		while(!stack.isEmpty()) {
			//-1을 넣어줌 
			result[stack.pop()] = -1;
		}
		
		//결과배열 돌면서 스트링빌더에 추가
		for(int num : result) {
			sb.append(num+" ");
		}
		
		//오등큰수 출력 
		System.out.println(sb);

	}

}