[프로그래머스] 디스크 컨트롤러

문제 링크 

프로그래머스

---

 

8번, 18번 테스트케이스에서 자꾸 틀려서 고생했다🥲

 

풀이

평균 대기 시간을 최소화하는 문제였다. 스케줄링 알고리즘을 기억하는 사람이라면 단번에 SJF(Shortest Job First) 알고리즘이라는 걸 알아챌 수 있다. (증명은 이 포스팅에서 다룰 문제가 아니므로 생략한다.)

현재 작업 큐에 들어온 일 중에 실행시간이 가장 짧은 일을 선택해야 하므로, 우선순위 큐를 이용하면 쉽게 풀 수 있다.

💡SJF(Shortest Job First)란?
작업 소요시간이 짧은 일부터 처리하는 스케줄링 알고리즘으로, 평균 대기 시간을 최소화할 수 있다.

 

0. 주의해야 할 점

1. jobs 배열은 정렬되지 않은 상태로 주어질 수 있다. 
2. 하드디스크가 작업을 수행하고 있지 않은 상태에서, 동시에 여러개의 작업 요청이 들어오면 수행시간이 짧은 작업부터 처리해야 한다.

 

1. jobs 배열 정렬하기

문제 조건에 jobs 배열이 정렬된 상태로 주어진다는 조건이 없으므로, 정렬을 먼저 해주어야 한다.

1. 요청 시간이 빠르고, 2. 수행 시간이 짧은 순서대로 정렬해주면 된다.

여기서 수행 시간이 짧은 순서대로 정렬하는 걸 빼먹으면, 8번&18번 테스트 케이스에서 틀렸습니다를 받게 된다🥲

Arrays.sort(jobs, (o1, o2) -> {
    if(o1[0]==o2[0]) return o1[1]-o2[1];
    return o1[0]-o2[0];
});

 

 

2. 작업 수행하기

• nowTime: 현재 시간을 의미하는 변수
• idx: jobs 배열의 인덱스

1. 작업 큐에서 수행시간이 가장 짧은 작업을 꺼내 수행한 뒤, nowTime을 작업의 종료 시간으로 갱신한다.

2. 시간이 흐른 사이 새로 요청된 작업을 작업 큐에 추가한다. (nowTime >= jobs[idx][0]인 경우)

3. 디스크가 일을 할당받지 않은 채로 대기하는 경우, 잠시 작업 큐가 비게 된다.

    (1) 다음 작업 jobs[idx]를 큐에 추가한다.

    (2) nowTime을 다음 작업의 시작시간으로 갱신한다.

4. 작업 큐가 빌 때까지 1~4를 반복한다.

pq.add(new Work(jobs[0][0], jobs[0][1]));
int nowTime = jobs[0][0];	// 현재 시간
int idx = 1;		// jobs 배열의 인덱스
while(!pq.isEmpty()) {
    Work work = pq.poll();
    answer += (nowTime - work.startTime + work.workTime);
    nowTime += work.workTime;

    while(idx<jobs.length && jobs[idx][0]<=nowTime) {
        pq.add(new Work(jobs[idx][0], jobs[idx][1]));
        idx++;
    }

    if(pq.isEmpty() && idx<jobs.length) {
        nowTime = jobs[idx][0];
        pq.add(new Work(jobs[idx][0], jobs[idx][1]));
        idx++;
    }
}

 

---

전체 코드

 

import java.util.*;

class Work implements Comparable<Work>{
    int startTime;
    int workTime;
    
    public int compareTo(Work o) {
        return this.workTime - o.workTime;
    }
    
    public Work(int startTime, int workTime) {
        this.startTime = startTime;
        this.workTime = workTime;
    }
}

class Solution {
    PriorityQueue<Work> pq = new PriorityQueue<>();
    public int solution(int[][] jobs) {
        int answer = 0;
        
        Arrays.sort(jobs, (o1, o2) -> {
            if(o1[0]==o2[0]) return o1[1]-o2[1];
            return o1[0]-o2[0];
        });
        
        pq.add(new Work(jobs[0][0], jobs[0][1]));
        int nowTime = jobs[0][0];
        int idx = 1;
        while(!pq.isEmpty()) {
            Work work = pq.poll();
            answer += (nowTime - work.startTime + work.workTime);
            nowTime += work.workTime;
            
            while(idx<jobs.length && jobs[idx][0]<=nowTime) {
                pq.add(new Work(jobs[idx][0], jobs[idx][1]));
                idx++;
            }
            
            if(pq.isEmpty() && idx<jobs.length) {
                nowTime = jobs[idx][0];
                pq.add(new Work(jobs[idx][0], jobs[idx][1]));
                idx++;
            }
        }
        
        return answer/jobs.length;
    }
}