[백준] 17299번 오등큰수 JAVA

오등큰수 문제

처음에 문제를 읽고 이게 무슨 소리야 했는데

이전 문제엿던 오큰수를 활용한 문제였다

 

오큰수는

인덱스를 저장하는 스택과

입력받은 데이터 array를 활용해 푸는 거였다면

 

인덱스를 저장하는 스택과

입력받은 데이터 array를 가지고 등장 횟수를 카운트해서 만든 맵을 활용 해 풀었다.

map 안에

입력받은 데이터의 등장 횟수를 for문을 돌려서 넣어주고

 

다시 입력받은 수만큼 for문을 돌며

오른쪽 숫자의 등장 횟수를 map에서 찾아서 현재 인덱스의 등장 횟수보다 클 경우 정답 배열에 입력해주는 식으로 풀었다.

 

 

import javax.management.ObjectName;
import java.io.*;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class Main {
    public static void main(String args[]) throws IOException, InterruptedException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(reader.readLine());
        String[] strArr = reader.readLine().split(" ");
//        StringBuilder result = new StringBuilder();
        int[] intArr = new int[num];
        int[] ansArr = new int[num];
        Map<Integer, Integer> cntMap = new HashMap<>();

//      숫자 배열에 넣는 작업
        for(int i = 0; i < num; i++){
            intArr[i] = Integer.parseInt(strArr[i]);
        }
//      등장횟수를 카운트해서 map에 넣는다
        for(int obj : intArr){
            int cnt = 0;
            if(cntMap.containsKey(obj)){
                cnt = cntMap.get(obj);
            }
            cntMap.put(obj, ++cnt);
        }

//      오큰수와 거의 비슷하게 구현
        Stack<Integer> indexStack = new Stack<>();
        indexStack.push(0);
        for(int i = 1; i < num; i++){
           if(indexStack.isEmpty()){
               indexStack.push(i);
           }
//           map에서 등장횟수를 찾아서 비교한다. 대신 입력은 입력배열의 값으로 입력
           while(!indexStack.isEmpty() && cntMap.get(intArr[indexStack.peek()]) < cntMap.get(intArr[i])){
               ansArr[indexStack.pop()] = intArr[i];
           }
           indexStack.push(i);
        }
        while (!indexStack.empty()) {
            // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면 빌 때 까지
            ansArr[indexStack.pop()] = -1;
            // stack에 쌓인 index에 -1을 넣고
        }

        for (int i = 0; i < num-1; i++) {
            bw.write(ansArr[i] + " ");
        }

        bw.write("-1");
        bw.write("\n");

        reader.close();
        bw.flush();
    }
}