[BOJ/PriorityQueue] 백준 1781 - 컵라면 (Java)

백준 1781 - 컵라면

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

문제

N개의 문제를 주고 각각의 문제를 풀었을 때 컵라면 몇 개 줄 것인지 제시
문제를 푸는데는 단위 시간 1 걸리며, 각 문제의 데드라인 <= N
각 문제를 풀 때 받을 수 있는 컵라면 수, 최대로 받을 수 있는 컵라면 수 < $2^{31}$

입력
첫 줄: 숙제의 개수 N (1 <= N <= 200,000)
다음 줄 ~ N + 1 줄:  i + 1번째 줄에 i번째 문제에 대한 데드라인, 풀면 받을 수 있는 컵라면 수
출력: 받을 수 있는 최대 컵라면 수

---

풀이

하루에 한 문제만 풀 수 있고 데드라인 d인 문제는 d일까지 해결해야 함

-> 마감일(`deadline`) 기준으로 가능한 만큼 문제 넣고 IF. 풀이 가능 수 초과 -> 라면 가장 적은 문제 버림

=> 그 시점까지 풀 수 있는 문제 수 넘기면 라면 적은 문제 버림

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

Arrays.sort(arr, (a, b) -> a[0] - b[0]);

 

• `PriorityQueue<Integer> pQ = new PriorityQueue<>()`: 현재까지 푼 라면 수 저장
• `pq.size() > deadline`: 현재 날짜(`deadline`)보다 더 많이 문제 품 
  • -> `pQ.poll()`: 가장 적은 라면을 주는 문제 버림

PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
    int deadline = arr[i][0];
    int ramen = arr[i][1];

    pQ.add(ramen);

    if (pQ.size() > deadline) pQ.poll();
}

---

코드

import java.io.*;
import java.util.*;

// 컵라면
public class boj_1781 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            int deadline = arr[i][0];
            int ramen = arr[i][1];

            pQ.add(ramen);

            if (pQ.size() > deadline) pQ.poll();
        }

        long total = 0;
        while (!pQ.isEmpty()) total += pQ.poll();

        System.out.println(total);
    }
}