[BaekJoon] 1781 컵라면 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

1. Problem을 deadline순으로 Sort한다.
2. 정렬된 Problem을 deadline이 적은 순대로 하나씩 PriorityQueue에 넣어주며 현재 시간보다 문제의 deadline이 작을 경우 가장 작은 값을 poll해주며 가장 reward가 높은 문제들을 갖게 한다.
3. PriorityQueue에 들어있는 reward의 합을 구한다.

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int maxDeadline = 0;
		StringTokenizer st;
		PriorityQueue<Problem> queue = new PriorityQueue<>();
		for (int i=0; i< N;i++) {
			st = new StringTokenizer(br.readLine());
			int deadline = Integer.parseInt(st.nextToken());
			int reward = Integer.parseInt(st.nextToken());
			queue.add(new Problem(i+1, deadline, reward));

		}

		
		PriorityQueue<Integer> resultQueue = new PriorityQueue<>();
		for (int i=1; i<=N; i++) {
			Problem p = queue.poll();
			resultQueue.add(p.reward);
			
			if (p.deadline < resultQueue.size()) {
				resultQueue.poll();
			}
		}
		
		int result = 0;
		while(!resultQueue.isEmpty()) {
			int poll = resultQueue.poll();
			result += poll;
		}
		System.out.println(result);
	}

}
class Problem implements Comparable<Problem>{
	int id;
	int deadline;
	int reward;
	
	public Problem(int id, int deadline, int reward) {
		this.id = id;
		this.deadline = deadline;
		this.reward = reward;
	}

	@Override
	public int compareTo(Problem o) {
		// TODO Auto-generated method stub

		return this.deadline < o.deadline? -1:1;
	}
}