[BOJ] 백준 [1781] 컵라면 JAVA

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

1781번: 컵라면

[문제]

[풀이]

문제의 조건을 만족하기위해선 데드라인을 만족과 동시에 컵라면을 제일 많이 받을 수 있는 쪽으로 해야한다.
현재 경과 일을 i 라고하면 , i 이상의 데드라인 문제들을 풀 수 있지만 
i 이전의 문제들을 풀 수 없다. 즉 , i 이상의 데드라인 문제들을 보면서 컵라면이 제일 많은 순으로 가져가야함.

경과일마다 처리해야하는 문제들을 1부터 차례대로 보기위해 데드라인순으로 우선 오름차순정렬을 한다.
그리고 정렬된 문제 리스트를 순회하면서 컵라면 오름차순으로 정렬된 우선순위큐에 넣는다.

만약 현재까지 경과된 일 수 보다 데드라인이 더 작은 문제가 나왓다 ?
그럼 우선순위큐에서 맨 위를 제거.

이것을 반복하다보면 우선순위큐엔 컵라면을 제일 많이 받을 수 있는 문제들만 남아 있을것이다

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Queue<int[]> list = new PriorityQueue<>((o1, o2) -> o1[0]-o2[0]); //데드라인 오름차순
        for(int i=0;i<N;i++)
            list.add(Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray());
 
        PriorityQueue<Integer> rest = new PriorityQueue<>();
        long answer=0;
        while (!list.isEmpty()){
            int[] quest = list.poll();
            rest.add(quest[1]);
            if(rest.size() > quest[0]) rest.poll();
        }
        while (!rest.isEmpty()) answer+=rest.poll();
 
        System.out.println(answer);
    }
}