[프로그래머스] 디스크 컨트롤러(자바) /Heap

문제 설명

 

제한사항

 

입력&출력

 

문제풀이

import java.util.*;

class Solution {
    static class job {
        int request;
        int time;

		public job(int request, int time) {
			this.request = request;
			this.time = time;
		}
	
    }
    public int solution(int[][] jobs) {
        int answer = 0;
        LinkedList<job> works = new LinkedList<>();
        PriorityQueue<job> pq = new PriorityQueue<>(new Comparator<job>() {
    		@Override
    		public int compare(job i, job j) {
    			return i.time - j.time;
    		}
    	});
        
        for(int i = 0 ; i < jobs.length;i++){
            works.add(new job(jobs[i][0],jobs[i][1]));
        }
        Collections.sort(works,new Comparator<job>() {
    		@Override
    		public int compare(job i, job j) {
    			return i.request - j.request;
    		}
    	});
        
        int cnt = 0;
        int request = works.peek().request;
        while(cnt < jobs.length) {
    		while(!works.isEmpty() && works.peek().request <= request) {
    			pq.offer(works.pollFirst());
    		}
    		
    		if(!pq.isEmpty()) {
    			job job = pq.poll();
    			request += job.time;
    			answer += request - job.request;
    			cnt++;
    		} else {
    			request++;
    		}
    	}
    	
    	return answer / cnt;
    }
}

 

이 문제는 PriorityQueue를 이용하는 힙 문제입니다.

먼저 모든 작업을 LinkedList에 넣어줬습니다.
이때 요청을 기준으로 오름차순 정렬을 했습니다.
현재 시간 이하의 요청에 대한 작업은 PriorityQueue로 옮겨서 작업을 진행했습니다.
이때 또한 걸리는 시간을 기준으로 오름차순을 정렬을 했습니다.
작업이 완료 되면 answer에 더해줍니다. 작업이 없는 경우에는 요청 시작 시간만 늘려줍니다.