백준 13904번 과제 (JAVA)

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

13904번: 과제

 

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

저는 역순으로 생각하였습니다.

먼저 가장 늦은 시간부터 할 수 있는 일을 우선순위 큐에 넣었습니다.

그리고 해당 시간에 가장 큰 값을 더해주고 위의 방법을 반복하여 문제를 해결하였습니다.

 

package BOJ.greedy;

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

public class BOJ_13904 {
    public static class Work{
        int d;
        int w;
        public Work(int d,int w){
            this.d = d;
            this.w = w;
        }
    }
    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<Work> list = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine());
            int d = stoi.apply(st.nextToken());
            int w = stoi.apply(st.nextToken());
            list.add(new Work(d,w));
        }

        int result = cal(list,n);
        System.out.println(result);
    }

    private static int cal(List<Work> list, int n) {
        Collections.sort(list,(v1,v2)->{
            return v2.d - v1.d ;
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int result = 0;
        int index = 0;
        for(int day = 1000 ; day > 0  ; day--){
            while(index < n && list.get(index).d >= day){
                pq.offer(list.get(index).w);
                index++;
            }
            if(!pq.isEmpty()){
                result += pq.poll();
            }
        }
        return result;
    }
}