프로그래머스_디스크 컨트롤러(JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

[문제 풀이]

우선순위 큐를 이용하여 문제를 풀었습니다.

디스크 콘트롤러 문제는 작업의 시작부터 작업이 끝나는 시간 길이의 최소 평균을 구하는 문제였습니다. 하나의 작업이 끝나는 시간안에 들어온 작업 중 가장 작업시간이 짧은 것을 선택하는 문제입니다.

 

구현방법은 아래와 같습니다.

1. jobs 배열을 시작 시간 순서대로 정렬 해줍니다.
2. 끝나는 시간이 짧은 것으로 정렬하는 우선순위큐를 생성합니다.
3. 우선순위큐에 작업의 시작시간이 현재 작업종료시간 보다 작은 것을 우선순위큐에 넣어줍니다.
4. 우선순위큐가 비어있다면 작업종료시간을 현재 작업의 시작시간으로 초기화합니다.
5. 우선순위큐가 비어있지 않다면 총걸린 시간에 현재 작업의 소요시간을 더해주고 들어온 시간을 빼줍니다.

[JAVA]

import java.util.*;

class Solution {

	public int solution(int[][] jobs) {

	int answer = 0;
		
        int cnt = 0;
        int current_index = 0;
        int current_end = 0;
        
        Arrays.sort(jobs, (obj1, obj2) -> obj1[0] - obj2[0]);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((obj1, obj2) -> obj1[1] - obj2[1]);
        
        while(cnt < jobs.length){
            
            while(current_index < jobs.length && jobs[current_index][0] <= current_end){
                pq.add(jobs[current_index++]);               
            }
            
            if(pq.isEmpty()){
                current_end = jobs[current_index][0];
            }
            else{
                int[] temp = pq.poll();
                answer += temp[1] + current_end - temp[0];
                current_end += temp[1];
                cnt++;
            }
            
        }
        
        return (int) Math.floor(answer / jobs.length);
	}
}