백준 17299번 오등큰수 [Java]

문제

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

 

코드

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

public class Main_17299 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer st= new StringTokenizer(br.readLine());
        HashMap<Integer, Integer> counts = new HashMap<>();
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            counts.put(A[i], counts.getOrDefault(A[i], 0) + 1);
        }
        int[] NGF = new int[N];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1; i < N; i++) {
            while(counts.get(A[stack.peek()]) < counts.get(A[i])) {
                NGF[stack.pop()] = A[i];
                if(stack.isEmpty()) break;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) {
            NGF[stack.pop()] = -1;
        }
        StringBuilder answer = new StringBuilder();
        for(int n : NGF) {
            answer.append(n).append(" ");
        }
        System.out.println(answer);
    }

}

 

접근방법

백준에 오큰수 문제랑 거의 유사했다. 오큰수는 오른쪽에 있는 숫자랑 비교했다면 미리 입력을 받으면서 개수를 세서 개수랑 비교를 했다.

counts는 처음에 잘못생각해서 counts의 개수가 유동적이니까 hashmap을 써야겠다고 생각했었다.

하지만 어차피 주어지는 max값이 있으니까 그거에 맞춰서 배열을 만드는게 더 메모리적으로 괜찮을거 같다.