프로그래머스 디스크 컨트롤러 (Level3 Java)

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

---

문제

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.

1. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.
2. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
3. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
4. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.

예를 들어

- 0ms 시점에 3ms가 소요되는 0번 작업 요청

- 1ms 시점에 9ms가 소요되는 1번 작업 요청

- 3ms 시점에 5ms가 소요되는 2번 작업 요청

 

작업 번호	요청 시각	작업 종료 시각	반환 시간
0번	0ms	3ms	3ms(= 3ms - 0ms)
1번	1ms	17ms	16ms(= 17ms - 1ms)
2번	3ms	8ms	5ms(= 8ms - 3ms)

우선순위 디스크 컨트롤러에서 모든 요청 작업의 반환 시간의 평균은 8ms(= (3ms + 16ms + 5ms) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해 주세요.

 

제한 사항

• 1 ≤ jobs의 길이 ≤ 500
• jobs[i]는 i번 작업에 대한 정보이고 [s, l] 형태입니다.

 

입출력 예

jobs	return
[[0, 3], [1, 9], [3, 5]]	8

입출력 예 설명

입출력 예 #1

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

---

문제 해결을 위한 과정

이 문제는 언제 작업을 큐에 넣을 것인가와 어떤 작업을 먼저 꺼낼 것인가를 동시에 해결해야 합니다.

1. 초기 정렬: 먼저 들어온 요청부터 확인해야 하므로, jobs 배열을 요청 시각(jobs[0]) 기준으로 오름차순 정렬합니다. (입력 데이터가 순서대로가 아닐 수 있음)
2. 데이터 구조화: 작업의 정보를 담을 Process 클래스를 정의합니다. 여기서 compareTo를 통해 소요 시간이 짧은 순으로 우선순위를 설정합니다.
3. 대기열 관리:
   • 현재 시간(current)까지 들어온 모든 요청을 우선순위 큐(pq)에 넣습니다.
   • 만약 큐가 비어있다면, 다음 작업의 요청 시각으로 현재 시간을 점프시킵니다.
4. 작업 실행: 큐에서 가장 소요 시간이 짧은 작업을 꺼내 실행합니다.
   • 현재 시간 = 현재 시간 + 작업 소요 시간
   • 반환 시간 = 현재 시간 - 요청 시각
5. 평균 계산: 모든 작업이 끝날 때까지 반복한 후, 총 반환 시간을 작업 개수로 나눕니다.

---

소스코드

import java.util.*;

class Solution {
    static PriorityQueue<Process> pq = new PriorityQueue<>();
    
    static class Process implements Comparable<Process> {
        int time;      // 소요시간
        int reqTime;   // 요청시각
        int idx;       // 작업번호
        
        public Process(int time, int reqTime, int idx) {
            this.time = time;
            this.reqTime = reqTime;
            this.idx = idx;
        }
        
        @Override
        public int compareTo(Process o) {
            int result = 0;
            result = this.time - o.time;
            if(result == 0) {
                result = this.reqTime - o.reqTime;
                if(result == 0) {
                    return this.idx - o.idx;
                }
                return result;
            }
            return result;
        }
    }
    
    public int solution(int[][] jobs) {
        int answer = 0;
        int current = 0;
        int num = 0;
        int index = 0;
        
        Arrays.sort(jobs, (o1, o2) -> {
            return o1[0] - o2[0];
        });
            
        while(num != jobs.length) {
            
            while(index < jobs.length && jobs[index][0] <= current) {
                pq.offer(new Process(jobs[index][1], jobs[index][0], index));
                index++;
            }
            
            if(pq.size() == 0) {
                current = jobs[index][0];
                continue;
            }
            
            Process temp = pq.poll();
            current += temp.time;
            answer += (current - temp.reqTime);
            num += 1;
        }
        
        answer /= num;
        return answer;
    }
}