[042] 17299. 오등큰수

✨ 알고리즘 분류 : 스택, 자료 구조

 

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

17299번: 오등큰수

 

 

---

 

 

 

 

🪡 문제에서 요구하는 조건 정리

 

- 자신의 오른쪽에 위치한 수 중에 등장 횟수가 자신보다 많은 수를 출력

- 오등큰수가 없다면 -1을 출력

- 등장 횟수는 수열 전체에서 count

 

 

🧶 풀이과정 

 

바로 어제 했던 오큰수의 응용 버전이다. 어제에 했던 오큰수에서 아주  조금만 응용하면 어렵지 않게 풀 수 있다.

여기에서 중요한 건 등장 횟수인데, 등장 횟수는 수열 전체에서 카운트를 하기 때문에 나는 Map을 사용했다. 같은 수의 등장은 count로 매기면 되기 때문에, 처음 입력을 받으면서 반복문을 진행할 때, map에 key값을 수열의 현재 수를, value에는 비어있을 경우 1, 아니면 +1을 하여 수를 계산하면 된다.

 

이후에는 오큰수와 같이 현재 arr[i]와 비교하여 덱에 있는 것이 더 작다면 덱에 있는 index를 res의 index로 하여 arr[i]의 값을 담는 형태로 진행한다.

 

 

 

🏹 제출코드

 

package data_structure_part_01;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Q17299 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        HashMap<Integer, Integer> map = new HashMap<>();
        Deque<Integer> deq = new ArrayDeque<>();

        int[] arr = new int[n];
        int[] res = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            int num = Integer.parseInt(st.nextToken());
            map.put(num, map.getOrDefault(num, 0) +1);
            arr[i] = num;
        }


        for(int i = 0; i < n; i++){

            while (!deq.isEmpty() && map.get(arr[i]) > map.get(arr[deq.peekLast()])){
                int po = deq.pollLast();
                res[po] = arr[i];
            }

            deq.offerLast(i);
        }

        while(!deq.isEmpty()){
            res[deq.pollLast()] = -1;
        }

        for(int i : res){
            bw.write(i + " ");
        }

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