15. 프로그래머스 - 디스크 컨트롤러 (힙)

문제 설명

하드디스크는 한 번에 하나의 작업만 처리할 수 있습니다. 이 문제에서는 "우선순위 디스크 컨트롤러"를 사용하는 가상의 시나리오를 고려합니다. 이 컨트롤러는 아래와 같은 방식으로 동작합니다:

1. 어떤 작업이 요청되면 [요청 시각, 소요 시간] 정보를 가진 채 대기 큐에 저장됩니다.
2. 하드디스크가 작업을 수행 중이 아니고, 대기 큐에 작업이 있다면 다음 조건에 따라 우선순위가 높은 작업을 선택하여 처리합니다:
   • 소요 시간이 짧을수록 우선순위가 높습니다.
   • 소요 시간이 같다면 요청 시각이 빠른 작업이 우선입니다.
   • 요청 시각도 같다면, 작업의 번호(입력 순서)가 빠른 작업이 우선입니다.
3. 하드디스크는 작업이 끝나는 순간, 바로 새로운 작업을 시작할 수 있습니다. 이때 소요되는 시간은 없다고 가정합니다.
4. 어떤 작업이 끝나는 시각에 새로운 작업 요청이 들어올 수도 있습니다. 이 경우, 새 작업은 즉시 대기 큐에 추가됩니다.

---

반환 시간 (Turnaround Time)

각 작업의 반환 시간은 작업 종료 시각 - 요청 시각으로 정의됩니다.

모든 작업이 끝났을 때, 평균 반환 시간의 정수 부분을 결과로 반환해야 합니다.

---

입력

• jobs: [요청 시각, 소요 시간] 형태의 작업 배열 (길이: 1 이상 500 이하)
  • 0 ≤ 요청 시각 ≤ 1000
  • 1 ≤ 소요 시간 ≤ 1000

---

출력

• 모든 작업의 평균 반환 시간의 정수 부분을 반환하세요.

---

예시

입력:

jobs = [[0, 3], [1, 9], [3, 5]]

처리 과정:

• 0ms: 0번 작업 시작 → 3ms에 완료 (반환 시간 3)
• 3ms: 2번 작업 시작 → 8ms에 완료 (반환 시간 5)
• 8ms: 1번 작업 시작 → 17ms에 완료 (반환 시간 16)

반환 시간 평균: (3 + 5 + 16) / 3 = 8

출력: 8

 

 

알고리즘 코드

import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]); // 작업들을 요청 시간 기준으로 정렬
        
        
        PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> a[1] - b[1]); // 작업 대기 큐
        
        int currentTime = 0;
        int index = 0; // jobs 배열의 포인터
        int totalTurnaroundTime = 0;
        int count = 0;
        
        while(count < jobs.length) {
            while(index < jobs.length && jobs[index][0] <= currentTime) {
                pq.offer(jobs[index]);
                index++;
            }
            
            if(!pq.isEmpty()) {
                int[] job = pq.poll();
                int requestTime = job[0];
                int duration = job[1];
                
                currentTime += duration;
                totalTurnaroundTime += (currentTime - requestTime);
                count++;
            }else {
                currentTime = jobs[index][0];
            }
        }
        
        return totalTurnaroundTime / jobs.length;
    }
}

 

우선순위 디스크 스케줄링 문제를 해결하기 위해 그리디 + 힙 방식으로 접근해봤다.

 

먼저 jobs : [요청 시간, 소요 시간] 쌍으로 주어지는 작업 목록

우리의 목표는 모든 작업의 시간 평균의 정수 부분을 구하는 것이다.

 

작업들을 요청 시간 기준으로 오름차순으로 정렬하고 우선 순위 큐를 사용해서 소요 시간이 짧은 작업이 먼저 나오도록 하였다.

즉 현재 시간에 처리 가능한 작업들 중 가장 빨리는 작업부터 처리하도록 하는 코드이다.

 

첫 번째 while문은 작업을 전부 처리할 때까지 반복하는 루프이고

그 다음 while문은 현재 시간까지 들어온 작업들을 대기 큐에 추가하는 루프이다.

그 후 if(!pq.isEmpty())을 통해 대기 큐에서 우선순위가 가장 높은 작업을 먼저 꺼내서 현재 시간에 처리하고, 해당 작업의 반환 시간을 누적해 주었다.

 

만일 대기 큐가 비어 있다면 다음 작업 요청 시간으로 점프해 주었다. 마지막에 반환 시간 평균의 정수 부분을 구해주면 끝난다.

 

시간 복잡도 분석

정렬 : O(N log N)

큐 삽입 / 삭제 :  O(N log N)

기타 루프 내부 연산 : O(N)

따라서 전체 시간 복잡도는 O(N log N)이다.