[백준 1781] 컵라면(Java)

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

이 문제는 그리디 알고리즘과 우선순위 큐를 이용하여 풀 수 있습니다.

문제에서 요구하는 최대의 컵라면을 받기 위해선 크게 2가지를 고려해야 합니다.

1. 작은 데드라인부터 탐색하면서 현재 데드라인에서 가장 많은 컵라면을 선택
2. 현재 데드라인의 컵라면 수가 이전 데드라인의 컵라면 수보다 많을 경우 현재값으로 대체

이를 위해 우선순위 큐를 이용합니다. 문제에서 주어진 데드라인과 컵라면 수를 1. 데드라인이 작은 순서대로 2. 컵라면 수가 많은 순서대로 우선순위 큐에 넣어 저장합니다. 이렇게 하면 1번의 요구사항을 만족합니다.

여기서 2번 요구사항 만족을 위해서 유저가 보유 중인 컵라면 수를 우선순위 큐로 오름차순 정렬하여 구성합니다. 이 때 우선순위 큐의 사이즈가 현재 데드라인이 되고, 그 내부의 값은 컵라면 수가 됩니다. 이 때 큐의 사이즈보다 데드라인이 클 경우 현재 데드라인 기준 가질 수 있는 라면이기 때문에 큐에 추가합니다. 그 외의 경우 큐의 최솟값과 현재값의 컵라면 수와 비교하여 더 큰 값으로 값을 대체합니다. 이런 식으로 하면 큐에는 최댓값들만 저장되기 때문에 큐의 원소들의 총 카운드가 정답이 됩니다.

다음은 코드입니다.

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());
        PriorityQueue<Ramen> queue = new PriorityQueue<>();
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            queue.add(new Ramen(d,n));
        }

        long cnt = 0;
        PriorityQueue<Integer> user = new PriorityQueue<>();
        while(!queue.isEmpty()){
            Ramen curr = queue.poll();
            if(user.size() < curr.deadline) user.add(curr.num);
            else{
                int min = user.peek();
                if(min < curr.num){
                    user.poll();
                    user.add(curr.num);
                }
            }
        }

        while(!user.isEmpty()){
            cnt += user.poll();
        }
        System.out.println(cnt);
    }

    static class Ramen implements Comparable<Ramen>{
        int deadline;
        int num;

        Ramen(int deadline, int num){
            this.deadline = deadline;
            this.num = num;
        }

        @Override
        public int compareTo(Ramen o) {
            if(this.deadline == o.deadline) return o.num - this.num;
            else return this.deadline - o.deadline;
        }
    }
}