백준 1781번 컵라면 (JAVA)

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

1781번: 컵라면

 

저는 해당 문제를 우선순위 큐를 이용해 문제를 해결하였습니다.

저는 데드라인을 역순으로 생각하였습니다. 데드라인이 n인 것들은 1 ~ n-1에서 풀수 있고 n-1은 1~n-2 ... 이렇게 풀 수 있습니다.

시간이 0 이라면 1 ~ n까지의 데드라인의 문제를 풀 수 있고, 1이라면 2 ~ n의 문제를 풀 수 있습니다.

역으로 보자면 , n-1의 시간에는 데드라인이 n인 문제를 풀 수 있고, n-2의 시간에는 n-1 ~ n 의 문제를 풀 수 있습니다.

저는 시간을 역순으로 해당 시간보다 큰 데드라인을 우선순위 큐에 넣고 그 시간에 풀 수 있는 가장 많이 컵라면을 주는 것을 리턴하고 이를 결과에 더하면서 문제를 해결하였습니다.

 

package BOJ.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1781 {
    private static class Problem{
        int deadLine;
        int reward;

        public Problem(int deadLine, int reward) {
            this.deadLine = deadLine;
            this.reward = reward;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," " );
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        List<Problem> input = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine()," " );
            int deadLine = stoi.apply(st.nextToken());
            int reward = stoi.apply(st.nextToken());
            input.add(new Problem(deadLine,reward));
        }
        Collections.sort(input,(o1,o2)->{
            if(o1.deadLine == o2.deadLine){
                return o2.reward - o1.reward;
            }
            return o2.deadLine - o1.deadLine;
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int index = 0;
        int result = 0;
        for(int deadLine = n ; deadLine >= 1 ; deadLine--){
            while(index < input.size()){
                Problem problem = input.get(index);
                if(problem.deadLine >= deadLine){
                    pq.offer(problem.reward);
                    index++;
                }else{
                    break;
                }
            }
            if(!pq.isEmpty()){
                result += pq.poll();
            }
        }
        System.out.println(result);
    }
}