[백준] 2109: 순회강연 - Java (우선순위 큐)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 
 
 

  접근 방식

 
이 문제의 알고리즘 분류는 그리디 알고리즘, 정렬, 우선순위 큐이다. 이 문제를 정렬과 우선순위 큐로 구현을 해보려고 한다.
먼저 강의들의 date 값을 기준으로 small -> Large 순(오름차순)으로 정렬을 한다. 
이제 하나씩 큐에 넣는다. 넣을 때 우리가 해줘야 하는 것들은 다음과 같다.
 
  1. 요소의 pay 값을 큐에 넣는다.
  2. 만약 큐의 size 가 해당 요소의 date 값을 초과한다면 가장 작은 값을 pop 한다.
 
이렇게만 보면 상당히 간단한데, 이렇게 구현하면 문제를 풀 수 있다. 사실 여기까지 생각하는 게 힘들 뿐이다.


2109번 문제의 기본 예제를 예를들어 설명해 보려고 한다.
 
왼쪽이 원본 배열이고, 오른쪽이 정렬 후의 배열이다.

 
 
이제 하나씩 큐에 넣어보자.
 
 
1. 
첫 번째 요소인 { p: 20, d: 1 } 이 들어갈 것이다. 
d == 1 >= priorityQueue.size() == 1 이므로 계속 진행한다.
 

 
 
2.
두 번째 요소인 { p: 2, d: 1 } 을 넣어준다.
d == 1 < priorityQueue.size() == 2 이다. 이러면 날짜가 중복되니 가장 높은 값들을 유지하기 위해서 가장 낮은 값을 제거해 준다.
(2 제거)
 

 
 
3.
세 번째 요소인 { p: 100, d: 2 } 인 요소를 넣어보자.
d == 2 >= priorityQueue.size() == 2  이므로 그래도 계속한다.
 

 
 
4.
네 번째 요소 { p: 8, d: 2 } 를 넣자.
d == 2 < priorityQueue.size() == 3 이므로 가장 작은 값인 8을 제거한다.
 

 
 
이렇게 반복하면 최댓값을 유지하면서 최댓값 보다 낮은 값들을 제거해 나갈 수 있다.
 
 
 

  풀이

 
 

package src.DataStructure.PriorityQueue;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class 순회강연_2109 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        int[][] arr = new int[N][2];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
        }

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });

        for(int i = 0; i < N; i++){
            priorityQueue.add(arr[i][0]);

            if(priorityQueue.size() > arr[i][1]){
                priorityQueue.poll();
            }
        }

        int result = 0;

        while(!priorityQueue.isEmpty()){
            result += priorityQueue.poll();
        }

        System.out.println(result);


    }
}