디스크 컨트롤러

문제

프로그래머스

작업 순서를 설정해 작업 시간을 최소로 하는 문제이다.

예를 들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

그림으로 표현하면 아래와 같다.

이것을 차례대로 처리하면 아래 그림과 같다.

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 된다.

 

하지만 A → C → B 순서대로 처리하면

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 된다.

---

우선순위큐를 사용해서 풀어야 하는 문제인것은 알았지만 어떤 순서로 정렬을 할지 몰랐다.

꽤나 까다로운 문제였다.

 

예를 들어 위에 예시에다가 [7, 1] 이 들어오면 어떻게 할까?

[0, 3]과 [2, 6] 이 끝난시점 9ms에 [7, 1]을 넣어야 할지 [1, 9]를 넣어야 할지 생각해줘야 한다.

 

일단 확실하는 것은 jobs를 시작 시간을 오름차순으로 정렬하고 순회하는 것까지는 알겠다.

 

처음에 current 라고 현재 시점을 저장해주는 변수를 선언하였다.

current 이하의 작업들은 우선순위 큐에 넣어서 처리해주었다.

우선순위 큐의 조건은 처리시간이 짧을 순서대로 넣었다.

 

위에 예시에서보 봤듯이 [0, 3], [1, 9], [2, 6] 은 결국 [0, 3], [2, 6], [1, 9] 로 처리되었다.

class Work implements Comparable<Work>{
    int start; //시작 시간
    int processTime; //작업 시간
    
    Work(int start, int processTime){
        this.start = start;
        this.processTime = processTime;
    }
    
    @Override
    public int compareTo(Work w){ //작업 시간 순서대로 오름차순
        return this.processTime - w.processTime;
    }
}

PriorityQueue<Work>pq = new PriorityQueue<>(); //작업 시간 순서대로
Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); //시작 시간 순서대로
        
int answer = 0;
int current = 0; //현재 시간

Work라는 새로운 클래스를 선언해 우선순위큐의 정렬조건을 정의해주었다.

int i = 0;
        while(i < jobs.length || !pq.isEmpty()){
            while(i <jobs.length && jobs[i][0] <= current){ //현재 시간 이하의 작업들을 큐에 넣어줌
                pq.add(new Work(jobs[i][0], jobs[i][1]));
                i++;
            }
            
            //큐가 비어있으면 현재 시간을 다음 작업의 시작시간으로 이동
            if(pq.isEmpty())current = jobs[i][0];
            else{ //현재 큐 안에 가장 작업시간이 작은 Work가 나옴
                Work w = pq.poll();
                answer += current + w.processTime - w.start;
                current+= w.processTime;
            }
        }

여기가 핵심 부분이다.

주석을 잘 살펴 보자.

---

전체 코드이다.

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<Work>pq = new PriorityQueue<>(); //작업 시간 순서대로
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); //시작 시간 순서대로
        
        int answer = 0;
        int current = 0; //현재 시간
        int i = 0;
        while(i < jobs.length || !pq.isEmpty()){
            while(i <jobs.length && jobs[i][0] <= current){
                pq.add(new Work(jobs[i][0], jobs[i][1]));
                i++;
            }
            
            //큐가 비어있으면 현재 시간을 다음 작업의 시작시간으로 이동
            if(pq.isEmpty())current = jobs[i][0];
            else{
                Work w = pq.poll();
                answer += current + w.processTime - w.start;
                current+= w.processTime;
            }
        }
        return answer / jobs.length;
    }
}
class Work implements Comparable<Work>{
    int start;
    int processTime;
    
    Work(int start, int processTime){
        this.start = start;
        this.processTime = processTime;
    }
    
    @Override
    public int compareTo(Work w){
        return this.processTime - w.processTime;
    }
}