디스크 컨트롤러

Posted on Edited on In , ,

문제정의

SJF(Shortest Job First)를 구현하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.*;

class Job implements Comparable<Job>{
    int request_time;
    int service_time;
    public Job(int request_time, int service_time)
    {
        super();
        this.request_time = request_time;
        this.service_time = service_time;
    }
    @Override
    public int compareTo(Job j)
    {
        return this.service_time - j.service_time;
    }

}

public class DiskController {

    //프로그래머스 문제풀이 level3 디스크 컨트롤러
    public static void main(String[] args) {
        int[][] jobs = {
            {0, 3},
            {1, 2},
            {500, 6},
            // {0, 7},
            // {0, 3},
        };

        Arrays.sort(jobs, (a,b) -> Integer.compare(a[0], b[0]));

        Queue<Job> prepare_q = new LinkedList<>();
        for(int i = 0; i < jobs.length; i++)
            prepare_q.add(new Job(jobs[i][0], jobs[i][1]));

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


        int time = jobs[0][0];
        int total_t = 0;
        int done = 0;
        
        
        while(done != jobs.length)
        {
            while(!prepare_q.isEmpty() && prepare_q.peek().request_time <= time)
                ready_q.add(prepare_q.poll());
            
            if(!ready_q.isEmpty())
            {
                Job job = ready_q.poll();
                time += job.service_time;
                total_t += time - job.request_time;
                done++;
            }
            else
                time = prepare_q.peek().request_time;
        }        

        System.out.println((int)Math.floor(total_t/done));

    }
    
}
작업을 나타내기 위한 클래스를 먼저 정의한다. 문제에서 주어진 입력대로 클래스의 인스턴스 변수는 request_time과 service_time이다. 여기서 비교 클래스를 상속받아 메소드를 오버라이딩 해주는데 인스턴스들을 정렬할 경우 service_time이 오름차순이 되도록 한다.

주어진 입력은 요청시간 순대로 들어오지 않으므로 이에 대해 람다식으로 정렬을 해주는 것이 우선이다. 람다식을 이용해 정렬한다.

정렬한 배열을 prepare_q에 전부 넣는다. 실은 여기서 개인의 취향대로 여기서도 우선순위 큐를 활용해도 된다. 이 큐는 처리되길 기다리는 작업들을 모아둔 것이라고 보면 된다.

이제 작업을 순차적으로 처리해야 한다. 초기 time을 첫번째 요청시간으로 초기화한다. total_t는 총 반환시간을 의미하며, done은 종료된 작업의 개수를 뜻한다.

반복은 모든 작업이 완료될 때 까지로 한다. 준비 큐(prepare_q)가 비어있지 않을 때, time보다 작거나 같은 요청시간을 가진 작업들을 모두 빼와 대기 큐(ready_q)에 집어넣는다. 이 때 대기 큐에 하나라도 들어가 있다면, 들어온 것 중에서 가장 작은 서비스시간을 가진 것을 꺼낸다. 그리고 time에는 서비스 시간을 더하고 total_t에 time-(요청 시간)을 더해준다. 그리고 done을 1증가한다. 만약에 대기 큐가 비어있다면 준비큐의 맨 앞의 요청시간을 time으로 갱신한다.

정렬을 사용하였기 때문에 작업의 개수를 n이라 하였을 때, 최종 시간복잡도는 \(O(nlogn)\)이다.

테스트



처음에는 우선순위큐를 이용하지 않고 dfs에서 방문기록을 남겼던 것 처럼, 배열을 정렬하고 방문기록을 활용하여 똑같은 논리로 짰었는데 계속 틀렸다. 어제 몇 시간을 고민하다. 결국 다 지우고 우선순위 큐로 구현하였더니 통과가 되었다. 그 전 코드의 문제점이 뭔지 알았으면 좋았을텐데, 앞으로 공부를 하면서 꼬인 논리를 지금 보다 더 능숙하게 풀어냈으면 좋겠다.