[백준] 1781번 '컵라면' - Java

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

1781번: 컵라면

---

문제

---

코드

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static class Node implements Comparable<Node> {
		int deadLine;
		int cup;
		
		public Node(int deadLine, int cup) {
			this.deadLine = deadLine;
			this.cup = cup;
		}
		
		@Override
		public int compareTo(Node node) {
			if(this.deadLine < node.deadLine) return -1;
			
			else if(this.deadLine == node.deadLine) {
				if(this.cup > node.cup) return -1;
				else if(this.cup == node.cup) return 0;
				else return 1;
			}
			
			else return 1;
		}
	}
	
	public static void main(String[] args) throws IOException {
		int n = Integer.parseInt(bf.readLine());
		
		Node[] arr = new Node[n];
		PriorityQueue<Integer> q = new PriorityQueue<>();
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int deadLine = Integer.parseInt(st.nextToken());
			int cup = Integer.parseInt(st.nextToken());
			
			arr[i] = new Node(deadLine, cup);
		}
		
		Arrays.sort(arr);
		
		for(Node a : arr) {
			if(q.size() < a.deadLine) {
				q.offer(a.cup);
			} else if(q.size() == a.deadLine) {
				int c = q.peek();
				if(c < a.cup) {
					q.poll();
					q.offer(a.cup);
				}
			}
		}
		
		long sum = 0;
		while(!q.isEmpty()) {
			sum += q.poll();
		}
		
		bw.write(sum + "\n");
		
		bf.close();
		bw.flush();
		bw.close();
	}
}

데드라인과 컵라면의 개수를 Node로 만들어서 정렬하였습니다.

정렬의 우선 순위는 먼저, 데드라인이 짧아야하고, 두번째로는 컵라면의 개수입니다.

 

우선순위 큐를 이용해 큐에 컵라면의 개수를 넣어 최종적으로 남아있는 컵라면의 개수를 모두 더한 값을 출력합니다.