[백준 1781] 컵라면 (JAVA)

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

1781번: 컵라면

 

아래의 우선순위로 정렬하고

1) 데드라인이 작은 것

2) 컵라면 수가 큰 것

 

풀 수 있는 문제의 컵라면 수를 넣어줄 우선순위큐를 생성한다.

포문을 돌려서 큐의 사이즈는 즉, 풀 수 있는 문제 수와 같기에

이를 문제의 데드라인과 비교하여 

큐의 사이즈보다 문제의 데드라인이 더 크다면 풀 수 있기에 큐에 넣고,

큐의 사이즈와 문제의 데드라인이 같다면 큐의 가장 작은 값을 peek하여 현재 문제의 컵라면 수와 비교한 후,

더 큰 값을 큐에 넣는다!! 

 

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

public class Main {
	static class Problem implements Comparable<Problem>{
		int deadLine, cupRamen;
		
		public Problem(int deadLine, int cupRamen) {
			this.deadLine = deadLine;
			this.cupRamen = cupRamen;
		}
		
		public int compareTo(Problem o) {
			if(o.deadLine == this.deadLine) {
				return o.cupRamen - this.cupRamen;
			}
			return this.deadLine - o.deadLine;
		}
	}
    
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		ArrayList<Problem> arr = new ArrayList<>();
		PriorityQueue<Integer> queue = new PriorityQueue<>(); // 가능한 문제들의 컵라면 수
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			arr.add(new Problem(d, c));
		}
		Collections.sort(arr);
		
		for(Problem problem : arr) {
			int size = queue.size();
			// 데드라인이 작다면 가능 
			if(size < problem.deadLine) {
				queue.offer(problem.cupRamen);
			}
			// 같은 날짜라면, 큐에 담겨진 가장 작은 라면수와 현재 라면수랑 비교하기 
			else if(size == problem.deadLine) {
				int peek = queue.peek();
				// 현재 라면이 크다면 큐에 있던것을 빼주고 현재 값으로 넣어주기 
				if(problem.cupRamen > peek) {
					queue.poll();
					queue.add(problem.cupRamen);
				}
			}
		}
        
		int max = 0;
		while(!queue.isEmpty()) {
			max += queue.poll();
		}
        
		System.out.println(max);
	}
	
}