백준 31860: 열심히 일하는 중(java)

문제

---

풀이

 

우선순위 큐를 이용하는 문제다.

PriorityQueue<Integer> queue=new PriorityQueue<>(Comparator.reverseOrder());

우선순위 큐 queue를 생성하되, 중요도가 높은 일부터 먼저 처리하게끔 해야 하므로 Comparator.reverseOrder()를 지정해야 한다. 

 

이후 queue에서 poll한 값을 K와 비교해 K 이하일 경우 삭제된 채로 continue하고, K 초과일 경우 이 값에서 M만큼 뺀 값을 다시 queue에 삽입한다.

 

위 과정을 queue가 공백 상태가 될 때까지 반복하고, 한 번 반복할 때마다 count를 1씩 증가시킨다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());
		
		PriorityQueue<Integer> queue=new PriorityQueue<>(Comparator.reverseOrder());
		
		for(int i=0; i<N; i++) {
			queue.add(Integer.parseInt(br.readLine()));
		}
		
		int count=0;
		int satisfaction=0;
		while(!queue.isEmpty()) {
			int todo=queue.poll();
			
			if(todo<=K) {
				continue;
			}
			
			queue.add(todo-M);
			count++;
			satisfaction=(satisfaction/2)+todo;
			sb.append(satisfaction+"\n");
		}
        
		System.out.println(count);
		System.out.println(sb);
	}
}