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

문제 보러가기

 

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

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

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

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

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

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

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

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예jobsreturn

jobs		return
[[0, 3], [1, 9], [2, 6]]		9

입출력 예 설명

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

 

[코드]

import java.util.Arrays; import java.util.Comparator; class Solution {     public int solution(int[][] jobs) {         int answer = 0; // 정답// 작업 요청대기시간         int index = 0; // 현재 시간         int idx = 0; // 작업의 번호         boolean check = true;         boolean[] visit = new boolean[jobs.length];         Arrays.sort(jobs, new Comparator<int[]>() { // 작업처리 요청시간이 빠른 순으로 정렬             @Override             public int compare(int[] o1, int[] o2) {                 if (o1[0] == o2[0]) return o1[1] - o2[1]; //만약 요청시간이 같다면 처리시간이 낮은 순으로 정렬                 return o1[0] - o2[0];             }         });         while (check) { //모든 작업을 처리했는지 확인             int min = Integer.MAX_VALUE;             for (int i = 0; i < jobs.length; i++) { //현재 시간과 맞지 않는 요청 시간의 작업을 미리 넣기                 if (visit[i]) continue;                 min = jobs[i][1];                 idx = i;                 break;             }             for (int i = 0; i < jobs.length; i++) { //현재 시간과 맞는 요청 시간의 작업 중 가장 처리시간이 낮은 작업 넣기                 if (visit[i]) continue;                 if (index >= jobs[i][0]) {                     if (jobs[i][1] < min) {                         min = jobs[i][1];                         idx = i;                     }                 }             }             if (index < jobs[idx][0]) index = jobs[idx][0]; // 만약 현재 처리시간에 들어오지 않은 요청 시간의 작업이 들어온 경우             index += min;             answer += index - jobs[idx][0];             visit[idx] = true;             check = false;             for (boolean b : visit) { //작업이 모두 처리 되었는지 확인                 if (!b) {                     check = true;                     break;                 }             }         }         return answer / jobs.length;     } }

[문제 풀이]

이 문제를 보고 SJF(Shortest Job First) 스케줄링 알고리즘이 생각났는데, 이 알고리즘은 작업 처리시간이 적은 작업부터 처리 하면서 작업 평균 대기시간을 최소한으로 줄이는 방법이다.

 

코드를 보면 작업 목록 배열을 처리 요청 시간 순으로 정렬을 한다. 정렬을 하는 이유는 문제 제한 사항에서

"하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다."라는 사항때문이다.

만약 지금 시간이 5초인데 남은 작업들의 작업 요청 시간이 7초, 6초인데 정렬을 하지 않았다면 7초가 먼저 처리될 수도 있다. 물론 for문을 돌려서 남은 작업에서 요청 시간이 가장 작은 작업을 골라서 해도 되지만 더 복잡해지니 정렬을 하는걸 권장한다.

 

다음으로 check는 모든 작업을 처리했는지 확인하는 방법으로 사용하였다.

순서대로 나열하면

1. 현재 시각과 상관없이 가장 빠르고 처리하지 않은 작업을 고르기

2. 현재 시각안으로 들어온 작업이 있다면 그 작업들 중에서 처리 시간이 가장 짧고 처리하지 않 작업을 고르기

3. 현재 시각안으로 들어온 작업이 없다면 현재 시각을 작업이 요청한 시간대로 맞추기

4. 작업 처리하기

5. 작업을 모두 처리했는지 확인 후 모두 처리되었다면 종료 아니라면 1번으로 돌아간다.

 

문제를 풀고나서 보니 이 문제는 Heap을 쓰는 문제였다.

그래서 다른 풀이를 가지고 왔다.

[코드]

import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; class Solution {     public int solution(int[][] jobs) {         int answer = 0;         int time = 0;         int index = 0;         Arrays.sort(jobs, (o1, o2) -> {             if (o1[0] == o2[0]) return o1[1] - o2[1];             return o1[0] - o2[0];         });         PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1])); //우선순위 큐         while (true) {             while (index < jobs.length && jobs[index][0] <= time) { //현재 시간내에 작업 넣기                 queue.add(jobs[index++]);             }             if (queue.size() == 0) { //현재 시간에 맞는 작업이 없을 경우                 time = jobs[index][0];                 continue;             }             int[] job = queue.poll();             time += job[1];             answer += time - job[0];             if (queue.size() == 0 && index == jobs.length) break; //모든 작업이 처리되었다.         }         return answer / jobs.length;     } }

사실 가져온 코드와 비교를 해보니 흐름은 비슷하다 생각이 든다. 그렇기에 이해하는데 긴 시간이 필요하지 않다.

다만 다른 부분이 있다면, 작업을 넣는 순서가 바뀌었고 모든 작업이 처리되었는지 확인하는 과정이 다르다는 점이다.

그렇지만 가독성면에서는 후자의 코드가 압승이기에 첫번째 코드의 방식대로 사용하지 않기를 권장한다.