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

1. 문제 이해

작업들의 요청에서 종료까지 걸린 시간의 평균을 최소화 --> 합을 최소화

분석 결과 진행중인 작업이 없을 때 들어온 작업 중 소요시간이 최소인 작업이 우선적으로 와야 됨!!

(일찍 들어온 작업이 여러번 더해지기 때문)

 

2. 전략

- Job 클래스 : require(요청 시점), take(소요시간)으로 이루어진 클래스

(Comparable 인터페이스 상속 --> take를 기준으로 오름차순 배열)

- pq 우선순위 큐 : Job클래스를 담는 큐. index에 요청된 작업들 담기

- index : 현재 시점

- target : 현재 진행 중인 작업

- tempR : 현재 진행 중인 작업의 요청 시점

- tempT : 현재 진행 중인 작업의 소요 시간 --> index 증가에 따라 감소시킴

- result : 작업들의 요청에서 종료까지 걸린 시간의 총 합

- num : 남은 작업의 개수

 

3. 참고했던 사항

priorityqueue의 구현방법

- class가 아닌 단순 타입으로 이루어진 경우에는 기본적으로 오름차순으로 정렬됨

PriorityQueue<Integer> pq = new PriorityQueue<>();

- 단순타입 + 내림차순 : Collections.reverseOrder()이용

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

- 클래스를 이용하는 경우 : Comparable 상속

class Job implements Comparable<Job>{
	int require;
    int take;
    Job(int r, int t){
    	this.require = r;
        this.take = t;
    }
    
    public int compareTo(Job j){
    	return this.take <= j.take ? -1 : 1; //오름차순
        //return this.take <= j.take ? 1 : -1; 
    }
}

PriorityQueue<Job> pq = new PriorityQueue<>();

**Collections.reverseOrder()를 통해 순서를 바꿀 수 도 있다.

(Collections.reverseOrder()는 비교순서 뒤집는 Comparator 객체 리턴)

PriorityQueue<Job> rq = new PriorityQueue<Job>(pq.size(), Collections.reverseOrder());
rq.addAll(pq);

 

 

4. 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        //Job 클래스(comparable)
        class Job implements Comparable<Job>{
            int require;
            int take;
            Job(int r, int t){
                this.require = r;
                this.take = t;
            }
            public int compareTo(Job j){
                return this.take <= j.take ? -1 : 1;
            }
        }
        //시점별 priority queue add& 판별
        PriorityQueue<Job> pq = new PriorityQueue<>();
        int index = 0, tempR = 0, tempT = 0, result = 0;
        int num = jobs.length;
        Job target = null;
        while(num > 0){
            for(int i = 0; i < jobs.length; i++){
                if(index == jobs[i][0])  {
                    pq.add(new Job(jobs[i][0], jobs[i][1]));
                }
            }
            if(tempT == 0){
                if(pq.size() != 0){ //새로운 job 선택
                    target = pq.poll();
                    tempR = target.require;
                    tempT = target.take;
                }
                else{ //선택할 job이 없음
                    index++;
                    continue;
                }
            }
            if(tempT > 0){
                tempT--;
                index++;
                if(tempT == 0){ //job이 끝남
                    result += (index - target.require);
                    num--;
                }
            }
        }
        answer = result/(jobs.length);
        return answer;
    }
}