[Java/자바 백준 1781] 컵라면

풀이

문제들을 deadLine이 작은 순, 받을 수 있는 컵라면 갯수가 큰 순으로 arraylist에 정렬했습니다.

 

컵라면을 최대한 많이 받으려면 deadline순으로 라면이 가장 많이 얻을 수 있도록 그리디하게 탐색해야하기 때문입니다.

 

PriorityQueue를 사용해서 queue를 minHeap이라고 생각해줍시다.

 

arr에 정렬되있는 값들을 탐색하면서

1. 큐 사이즈가 현재 데드라인보다 작다면 - 큐에 삽입을 해줍니다

 

2. 만약 큐 사이즈와 현재 데드라인이 같다면 큐의 peek(현재까지 얻을 수 있는 라면 중 가장 최솟값)과 비교를 해줍시다.

만약 peek가 작다면 빼주고 현재 라면수를 넣어주도록 합시다.

 

마지막으로 큐에 들어간 값들을 모두 더해주면 됩니다 !

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

public class Main {

	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<>();
		
		int max = 0;
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			int deadLine = Integer.parseInt(st.nextToken());
			int cupRamen = Integer.parseInt(st.nextToken());
			arr.add(new Problem(deadLine, cupRamen));
		}
		// 데드라인이 작고, 라면이 큰순으로 정렬하기 
		Collections.sort(arr);
		
		for(Problem problem : arr) {
			// 사이즈는 일(day)  수를 뜻함 
			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);
				}
			}
		}
		while(!queue.isEmpty()) {
			max += queue.poll();
		}
		System.out.println(max);
	}
	
	private static class Problem implements Comparable<Problem>{
		int deadLine, cupRamen;
		
		public Problem(int deadLine, int cupRamen) {
			this.deadLine = deadLine;
			this.cupRamen = cupRamen;
		}
		
		// deadline이 작은 순, 컵라면이 큰 순 
		public int compareTo(Problem o) {
			if(o.deadLine == this.deadLine) {
				return o.cupRamen - this.cupRamen;
			}
			return this.deadLine - o.deadLine;
		}
	}
}