[백준 17299] 오등큰수(Java)

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

이 문제는 스택을 이용하여 풀 수 있습니다.

https://velog.io/@gale4739/%EB%B0%B1%EC%A4%80-17298-%EC%98%A4%ED%81%B0%EC%88%98Java
백준 17298(오큰수) 문제와 굉장히 유사한 문제로 유사한 풀이과정을 보입니다.

오큰수 문제는 자기 자신보다 오른쪽에서 있으면서 큰 수 중 가장 왼쪽에 있는 수입니다. 따라서 스택에 인덱스를 저장하면서 오른쪽으로 계속 이동하다가 스택의 피크값보다 큰 값이 나타나게 된다면 스택 안에 저장되어 있는 인덱스의 값이 현재 값보다 클 때까지 현재 값으로 치환하빈다

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] A = new int[N];
        int[] C = new int[1000001];
        int[] res = new int[N];
        for(int i=0;i<N;i++){
            A[i] = Integer.parseInt(st.nextToken());
            C[A[i]]++;
            res[i] = -1;
        }

        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<N;i++){
            while(!stack.isEmpty() && C[A[stack.peek()]] < C[A[i]]){
                int idx = stack.pop();
                res[idx] = A[i];
            }

            stack.push(i);
        }

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