[프로그래머스 / Lv.3] - 디스크 컨트롤러 (Java)

문제

---

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

프로그래머스

 

---

문제 풀이

---

문제의 중요 포인트

• 작업 우선순위: 요청 시점과 소요 시간을 고려하여 가장 효율적인 작업 처리 순서를 결정하는 것이 중요하다.
• 우선순위 큐: 대기 중인 작업을 관리하기 위해 우선순위 큐를 사용하여 소요 시간이 짧은 작업을 우선 처리한다.
• 시간 관리: 현재 시간과 작업 완료 시간을 정확히 관리하여 대기 시간을 계산해야 한다.

해당 문제의 유형은 힙(Heap)이다.
우선순위 큐는 내부적으로 정렬 알고리즘으로 힙 정렬 방식을 사용한다.

우선순위 큐 내에서 사용하는 정렬 알고리즘은 일반적으로 힙(Heap) 구조를 기반으로 한다. 힙은 이진 트리 형태의 자료구조로, 각 노드가 자식 노드보다 우선순위를 가지고 있는 특성을 가진다.
1. 최소 힙(Min Heap): 부모 노드가 자식 노드보다 항상 작거나 같은 값을 가지며, 가장 작은 값이 루트 노드에 위치한다. 이 구조는 우선순위 큐에서 가장 높은 우선순위를 가진 요소(가장 작은 값)를 효율적으로 꺼낼 수 있게 해준다.
2. 최대 힙(Max Heap): 부모 노드가 자식 노드보다 항상 크거나 같은 값을 가지며, 가장 큰 값이 루트 노드에 위치한다. 이 경우, 높은 우선순위를 가진 요소(가장 큰 값)를 꺼낼 수 있다.
Java의 `PriorityQueue` 클래스는 기본적으로 최소 힙을 사용하여 구현되어 있으며, 이를 통해 작업의 우선순위에 따라 요소를 자동으로 정렬하고 관리한다.

 

풀이 과정

1. 정렬: 먼저 요청 시점을 기준으로 작업을 오름차순 정렬한다.
   
   • 문제를 잘 읽어보면 입력으로 들어오는 jobs 2차원 배열이 정렬된 상태로 들어온다는 조건이 없다.
2. 우선순위 큐 초기화: 소요 시간이 짧은 작업을 우선 처리하기 위해 우선순위 큐를 사용한다.
3. 작업 처리: 현재 시간에 도달한 모든 작업을 큐에 추가하고, 큐에서 가장 소요 시간이 짧은 작업을 꺼내 처리한다.
   
   1. 대기 시간 계산: 각 작업의 요청 시점과 종료 시간을 통해 대기 시간을 계산하고, 이를 합산하여 평균 대기 시간을 구한다

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int currentTime = 0; // 현재 시간
        int totalWaitingTime = 0; // 총 대기 시간
        int completedJobs = 0; // 완료한 작업 수
        
        // 요청되는 시점 오름차순 정렬
        Arrays.sort(jobs, Comparator.comparingInt(job -> job[0]));
        
        // 우선순위 큐: 소요 시간이 적은 작업을 우선 처리
        PriorityQueue<int[]> jobQueue = new PriorityQueue<>(Comparator.comparingInt(job -> job[1]));
        
        int jobIndex = 0; // 요청 리스트에서 현재 작업 인덱스
        
        while (completedJobs < jobs.length) {
            // 현재 시간에 도달한 모든 작업을 큐에 추가
            while (jobIndex < jobs.length && jobs[jobIndex][0] <= currentTime) {
                jobQueue.offer(jobs[jobIndex++]);
            }
            
            // 대기 중인 작업이 없으면 시간 증가
            if (jobQueue.isEmpty()) {
                currentTime = jobs[jobIndex][0]; // 다음 작업의 요청 시점으로 이동
                continue;
            }
            
            // 큐에서 작업 꺼내기 (소요 시간이 가장 적은 작업)
            int[] currentJob = jobQueue.poll();
            currentTime += currentJob[1]; // 작업 수행
            totalWaitingTime += currentTime - currentJob[0]; // 대기 시간 계산
            completedJobs++; // 완료한 작업 수 증가
        }
        
        // 평균 대기 시간 계산 (소수점 이하 버림)
        return totalWaitingTime / jobs.length;
    }
}