프로그래머스 - 힙 - 디스크 컨트롤러

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

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

 

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class 디스크_컨트롤러 {
    public static void main(String[] args) {
        디스크_컨트롤러 o = new 디스크_컨트롤러();
        System.out.println(o.solution(new int[][]{{0, 1}, {4, 3}}));
    }
 
    public int solution(int[][] jobs) {
        HardDisk hardDisk = new HardDisk(jobs);
        return hardDisk.process();
    }
 
    class HardDisk {
        private int[][] jobs;
        Queue<int[]> q = new PriorityQueue<int[]>((o1, o2) -> {
            int ret = o1[1] - o2[1];
            if(ret == 0) {
                ret = o1[0] - o2[0];
            }
            return ret;
        });
 
        public HardDisk(int[][] jobs) {
            this.jobs = jobs;
            init();
        }
 
        public void init() {
            Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
        }
 
        public int process() {
            int lastJobIndex = -1;
            int totalJobEndTime = jobs[0][0];
            int sumTaskTime = 0;
 
            while (!q.isEmpty() || lastJobIndex < jobs.length) {
                if(!q.isEmpty()) {
                    int[] curJob = q.poll();
                    int taskTime = 0;
 
                    if(curJob[0] < totalJobEndTime) {
                        totalJobEndTime += curJob[1];
                        taskTime = totalJobEndTime - curJob[0];
                    } else {
                        taskTime = curJob[1];
                        totalJobEndTime += curJob[1];
                    }
 
                    sumTaskTime += taskTime;
                }
                lastJobIndex = registerJob(lastJobIndex, totalJobEndTime);
            }
 
            return sumTaskTime / jobs.length;
        }
 
        private int registerJob(int lastJobIndex, int totalJobEndTime) {
            lastJobIndex++;
            int count = 0;
            for(int i = lastJobIndex; i<jobs.length; i++) {
                if(totalJobEndTime >= jobs[i][0]) {
                    q.offer(jobs[i]);
                    lastJobIndex = i;
                    count++;
                } else {
                    break;
                }
            }
            if(count == 0 && lastJobIndex < jobs.length) {
                q.offer(jobs[lastJobIndex]);
            }
 
            return lastJobIndex;
        }
    }
}
 

 

알고리즘

• 힙
• 굉장히 복잡하게 푼 느낌이다.. 이것 저것 고려해야할것이 많았다
• 힙을 이용해서 매순간 동적으로 우선순위를 정하면 된다.
• 알고리즘에 대해 설명하면

1. 작업들을 요청 순서대로 정렬.
2. 첫번째 작업과 같은 요청시간대의 작업들을 모두 큐에 넣는다. 리스트의 마지막 작업 인덱스를 기록해둔다(수행됐던 작업의 중복을 막기 위해)
3. 큐에서 하나의 작업을 빼서 작업을 진행한다.
4. 작업이 끝난 시간을 알아내고 그 시간 전에 요청한 작업이 있다면(마지막 작업 인덱스 이후의 작업 중에) 큐에 작업들을 넣는다. 작업이 끝난 시간 전에 요청한 작업이 없고 다음 작업이 남아 있다면 해당 작업을 큐에 넣는다.
5. 큐에 작업이 없고 마지막 작업 인덱스가 작업 리스트의 크기와 같다면 작업 종료. 작업이 끝난 최종시간과 작업 리스트의 크기를 나누어 리턴.