Programmers - 디스크 컨트롤러 with JAVA

 

 

문제

문제는 우선 디스크에 처리해야하될 작업들이 수행될 것이고

문제에는 작업들마다 작업이 디스크에 들어가는 시점과 소요시간이 묶여서 디스크에 들어간다.

이제 디스크를 처리할 때, (각 작업이 걸린 시간 + 작업이 디스크에 들어오고 기다린 시간) / 총 작업의 수 의 최소를 구하는 문제이다.

 

 

 

 아이디어 & 로직 & 코드

우선적으로 아이디어는 다음과 같다.

1. 만약 작업 대기 줄에 하나밖에 없다면 먼저 실행된다.

2. 두개 이상의 작업이 있다면 수행시간이 짧은 것을 먼저 실행시킨다.

• 결국에 구하는 값을 보면 총작업의 수는 고정이고 각 작업이 걸리는 시간도 고정이다 작업이 디스크에 들어오고 기다리는 시간이 짧을 수록 최소값을 구할 수 있는 구조인데, 걸리는 시간이 짧은 작업을 먼저 수행해야 다른 작업이 기다리는 시간이 짧아지므로 최소값을 갖는 구조인 것이다.

다시 설명해보면, 큐에 들어온 작업이 두개라고 가정하자. 작업들이 기다린 시간을 떠나서, 짧은 것을 빨리할수록 전체 시간은 짧아진다.

2초에 들어온 3초짜리 작업 vs 1초에 들어온 10초짜리 작업, 현재 시간은 3초

-> 10초짜리 작업을 먼저한다면 14 + 12

-> 3초짜리 작업을 먼저한다면 4 + 15

 

 

 

로직

1. 끝난 작업의 수(count) 가 총 작업의 수와 같아질 때까지 반복한다.

2. 현재 시간과 방문여부를 초기화 해두고 현재 시간보다 시작 시간이 작고 방문하지 않은 작업을 우선순위 큐에 넣는다.

(우선 순위 큐를 사용하는 이유는 앞서 설명한 것처럼 소요시간이 짧은 것을 먼저 실행시킴을 위함.)

3-1. 큐에 작업이 없다면 1초를 증가시키고

3-2. 작업이 있다면 마친 작업이 끝난 시간을 더한 시간이 현재 시간이 된다.

4. 마친 작업이 있다면 결과 값에 (작업의 소요시간 + 작업의 시작시간 - 요청이 들어온 시간) 을 더한다.

5. 모든 작업이 종료되었다면 결과값/작업의 수를 반환한다.

 

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<List<Integer>> queue 
            = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(1)));
        int time = 0;
        int count = 0;
        int answer = 0;
        boolean[] visited = new boolean[jobs.length];
        while(count < jobs.length){
            for(int i=0; i<jobs.length; i++){
                if(!visited[i] && jobs[i][0] <= time){
                    queue.add(Arrays.asList(jobs[i][0], jobs[i][1]));   
                    visited[i] = true;
                }
            }
            if(queue.size() > 0){
                List<Integer> check = queue.poll();
                answer += time-check.get(0)+check.get(1);
                time += check.get(1);
                count += 1;
            }
            else{
                time += 1;   
            }
        }
        return answer/jobs.length;
    }
}