[Programmers]-디스크 컨트롤러(힙)

문제

“코딩테스트 고득점 Kit - 힙(Heap)” 문제이다.

평균시간을 최소로 구해 반환해야한다.

처음에 BFS를 써야되는 줄 알았다.

구하는 식이 있었다.

1. 수행시간이 짧은 작업부터 처리한다.
2. 하나의 작업이 끝나는 시점에 들어온 모든 요청들에 대해 수행시간이 짧은 작업부터 처리해야한다.

전공 때 배운 SJF 스케쥴링 느낌이 났다.

코드

import java.util.PriorityQueue;
import java.util.LinkedList;
import java.util.Collections;

class Solution {
    public class Disk{
        int request;
        int work;
        public Disk(int request, int work){
            this.request = request;
            this.work = work;
        }
    }
    public int solution(int[][] jobs) {
        int answer = 0;
        
        LinkedList<Disk> list = new LinkedList<>();
        for(int[] job : jobs) list.add(new Disk(job[0], job[1]));
        Collections.sort(list, (j1,j2) -> j1.request - j2.request);//요청시간 정렬
        
        PriorityQueue<Disk> q = new PriorityQueue<>((d1, d2) -> d1.work - d2.work);//작업량순 큐
        
        int count = 0;
        int jobIndex = 0;
        int end = 0;
        while(count < list.size()){
            //작업이 끝나는 기준에 들어온 모든 요청작업을 큐에 담는다.
            while(jobIndex < list.size() && list.get(jobIndex).request <= end){
                q.offer(list.get(jobIndex++));
            }
            
	    //없는건 위while 조건 만족 안됨.
            if(q.isEmpty()){
                end = list.get(jobIndex).request;
            }
            else{//기준에 들어온 작업
                Disk data = q.poll();
                answer += data.work + end - data.request;//요청에서 종료까지
                end += data.work;
                count++;
            }
        }
        return answer / list.size();
    }
}

요약

• 굳이 링크드리스트를 안써도 되겠다. 내생각엔.
• 람다를 좀 더 익숙해졌다.