[프로그래머스]디스크 컨트롤러 - JAVA

[프로그래머스]디스크 컨트롤러

programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

풀이

이 문제의 개념은 CPU스케줄링의 비전섬 기법중 SJH스케줄링 기법이랑 완전히 동일하다. ReadyQueue에 있는 작업 중에 실행시간이 짧은 작업에게 먼저 CPU를 할당한다.

 

ReadyQueue는 우선순위 큐를 사용하여 실행시간이 짧은 순서대로 정렬되게 해주었고, 기존의 jobs는 시작시간 순서대로 정렬해 주었다.

 

반복문을 사용하여 현재 시간에서 처리할 수 있는 작업을 모두 q에 넣어주고 짧은 시간 순서대로 처리하여주었다. 만약 q가 비어있다면 현재 처리할 수 있는 작업이 없으므로 다음 작업의 시작시간으로 넘어간다. 

 

q가 비어있지 않다면 q에 맨 앞에있는 작업을 꺼내어 실행시킨 후 각 작업의 요청 ~ 종료 시간을 계산해 주어야 한다. 요청시간은 작업의 시작이간과 동일하고, 종료시간은 현재 시간에서 작업이 끝나는 시간을 더해준다. 그리고 종료시간에서 요청시간을 빼주어서 구한다. 작업이 끝나고 시작시간을 재 계산해준다.

 

요청 ~ 종료시간을 구하는 방법을 그림으로 살펴보면 아래와 같다.

C작업의 경우 jobs의 값은 [2, 6]이다 이때 2는 요청시간을, 6은 실행시간을 의미한다. 그리고 현재 시간은 A작업이 끝난 3이 된다. 이때 C작업의 요청 ~ 종료시간은 3(현재시간) + 6(C의 실행시간) - 2(C의요청시간) = 7이 된다.

 

 

 

 

코드

import java.util.*;
 
class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); //처리시간 순서대로
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); //시작시간 순서대로 
        
        int answer = 0;
        int current = 0; //현재 시간
        int i = 0;
        while(i < jobs.length || !q.isEmpty()) {
            while(i < jobs.length && jobs[i][0] <= current) {
                q.add(new int[] {jobs[i][0], jobs[i][1]});
                i++;
            }
            
            if(q.isEmpty()) { //큐가 비어있다. -> 현재 실행할 수 있는 작업이 없다.
                current = jobs[i][0]; //다음 작업의 시작시간으로 이동한다.
            } else {
                int[] temp = q.poll();
                answer += current + temp[1] - temp[0]; //요청 ~ 종료시간 
                current += temp[1];
            }
        }
        return answer / jobs.length;
        
    }
}