프로그래머스 알고리즘 고득점 Kit - [Lv.3] 디스크 컨트롤러 (Java)

문제 출처 - 링크

알고리즘 분류

• 힙(Heap)

📋 문제 요약 설명

• 작업은 [작업이 요청되는 시점, 작업의 소요시간] 구성으로 2차원 배열이다.
• 하드디스크는 한 번에 하나의 작업만 수행할 수 있고, 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행한다.
• 작업 단계
  1. 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면
     • 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킨다.
     • 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높다.
  2. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면
     • 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킨다.
     • 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있다. 이 과정에서 걸리는 시간은 없다고 가정한다.
• 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 해라

💡 알고리즘 설계 / 접근 방법

1. 배열을 작업의 요청 시점 기준으로 오름차순 정렬
2. 작업의 소요시간 기준으로 오름차순 정렬되는 대기큐 만들기
3. 모든 요청이 수행될 때까지 반복하기
   1. 요청 시간이 된 작업들을 대기큐에 넣는다.
   2. 대기큐가 비어있다면 남아있는 요청의 가장 빠른 요청 시점으로 작업이 끝난 시간을 맞춘다.
   3. 대기큐가 비어있지 않다면 남아있는 요청 중 수행시간이 가장 짧은 요청을 수행한다.
      1. 요청 작업의 반환 시간을 구한다.
      2. 작업이 끝난 시간을 갱신한다.

➕ 보완하기 / 성능 비교

• 만약 작업의 요청 시점이 작업이 끝난 시간(end)보다 훨씬 뒤인 작업이 남았다면 문제가 생기지 않을까?

  • if (pq.isEmpty()) 블록이 보장하는 "요청 전 작업 강제 점프"는 시간 흐름 단절을 방지 해준다.

    즉, 큐에 들어온 작업이 아무것도 없고(end 이전에 요청된 게 없고), 남은 작업들은 모두 future(미래)라면 현재 시간(end)을 미래 요청 시간으로 점프시킨다.
    

  • 작업 큐에 요청이 있으면 → 그대로 짧은 순서대로 처리한다. (최적화)

  • 작업 큐가 비어 있고, 남은 요청이 end보다 뒤이면 → end = 요청 시간 으로 점프한다.

✅ 풀이

시간 복잡도 → O(N log N) + O(N log N) = O(N log N)

1. Arrays.sort() : O(N log N)
2. while 루프 : 최대 O(N)
3. 내부 while 루프 : 누적 O(N)
4. pq.add() 및 pq.poll() : O(N log N)
   • O(log N) 작업이 N번 수행됨

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        // (int[] 배열을 첫 번째 원소 = 작업의 요청 시점) 기준으로 오름차순 정렬
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
        // (int[] 배열을 두 번째 원소 = 작업의 소요시간) 기준으로 오름차순 정렬되는 우선순위 큐(Heap)
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        
        int count = 0; // 수행된 요청 개수
        int jobsIdx = 0; // jobs 배열의 인덱스
        int end = 0; // 수행되고난 직후의 시간
        int sum = 0; // 반환 시간 총합      
		
        // 모든 요청이 수행될 때까지 반복
        while (count < jobs.length) {

			// 하나의 작업이 완료되는 시점(end)까지 들어온 모든 요청을 큐에 넣음
			while (jobsIdx < jobs.length && jobs[jobsIdx][0] <= end) {
				pq.add(jobs[jobsIdx++]);
			}

			// 큐가 비어있다면 작업 완료(end) 이후에 다시 요청이 들어온다는 의미
			if (pq.isEmpty()) {
				end = jobs[jobsIdx][0]; // 남아있는 요청의 "가장 빠른 요청 시점"으로 end를 맞춤
			} else { // 작업이 끝나기 전(end 이전) 들어온 요청 중 가장 수행시간이 짧은 요청부터 수행 
                int[] temp = pq.poll();
				sum += temp[1] + (end - temp[0]); // 작업 소요 시간 + 대기 시간=(작업이 끝난 시간 - 작업 요청 시점)
				end += temp[1]; // 현재 작업 끝나서 시간 갱신
				count++;                
			}
		}

		return (int) Math.floor(sum / jobs.length);        
    }
}