[JAVA CodingTest] 디스크 컨트롤러 (우선순위 큐, Comparator)

문제 설명

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

1. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.

2. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.

3. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.

4. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.

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

---

전체 코드

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

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));

		PriorityQueue<int[]> pq = new PriorityQueue<>(
                Comparator.comparingInt((int[] a) -> a[1])
        );

        int currentTime = 0;
        int index = 0; 
        int totalWaitTime = 0;
        int count = 0; 

        while(count < jobs.length){

            while(index < jobs.length && jobs[index][0] <= currentTime){
                pq.offer(jobs[index]);
                index++;
            }

            if(pq.isEmpty()){
                currentTime = jobs[index][0];
            }else {
                int tmpJob[] = pq.poll();
                currentTime += tmpJob[1];
                totalWaitTime += currentTime - tmpJob[0];
                count++;
            }

        }

        answer = totalWaitTime / jobs.length;
        
        return answer;
    }
}

---

1. 요청 시간 기준으로 정렬 ->소요 시간이 짧은 순서대로 정렬

작업을 먼저 "요청 순서"대로 처리하고, 실행할 수 있는 작업 중에서 "소요 시간이 짧은 것"을 먼저 실행하는 방식!

1) 배열을 요청 시간 기준으로 정렬

Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));

2) 소요 시간이 짧은 순서대로 정렬하는 우선순위 큐 만들기

 PriorityQueue<int[]> pq = new PriorityQueue<>(
 	Comparator.comparingInt((int[] a) -> a[1])
 );

 

인터페이스 Comparator<T> 란?

- JAVA에서 객체를 정렬할 때 사용하는 인터페이스

- Comparator은 기본 정렬 후, 추가적인 기준을 적용할 수 있다. 

Comparator 메서드

메서드	설명
compare(T o1, T o2)	두 객체 비교
Comparator.comparing(Function keyExtractor)	기준 정렬 (ex : .comparingInt(a -> a[0])
thenComparing(Function keyExtractor)	추가 정렬 기준
Collections.sort(list, comparator)	리스트 정렬
PriorityQueue<>(comparator)	우선순위 큐 정렬

 

내가 푼 첫 코드가 틀린 이유 

//내가 처음 접근한 방식
PriorityQueue<int[]> pq = new PriorityQueue<>(
    Comparator.comparingInt((int[] a) -> a[1]) // 두 번째 원소(소요 시간) 기준 정렬
              .thenComparingInt(a -> a[0]) // 첫 번째 원소(요청 시간) 기준 정렬
);

처음에 이렇게 풀었는데, 작업을 가장 먼저 요청된 작업부터 처리해야 하기 때문에 이 비교는 틀렸다. 

 

• Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
  → 작업을 먼저 "요청 시점" 기준으로 정렬해서 가장 먼저 요청된 작업부터 처리할 수 있도록 함.
• PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
  → 큐에서는 실행 시간이 짧은 작업을 우선 실행.
• Arrays.sort(jobs, Comparator.comparingInt(a -> a[0])); 없이 바로 pq에 넣으면 요청 시간이 아닌 소요 시간을 기준으로 먼저 정렬됨.
  → 즉, "가장 먼저 요청된 작업"이 아니라, "소요 시간이 짧은 작업"이 먼저 실행될 수 있음.

 

2. 변수 설정 

int currentTime = 0; //현재 시간
int index = 0; //jobs 배열의 인덱스
int totalWaitTime = 0; //반환 시간 
int count = 0; //처리된 작업의 수

 

3. 반복문 

1) 처리된 작업의 수가 전체 작업의 수보다 작을 때 반복 

while(count < jobs.length){ 

...

}

 

2) 현재 시간보다 먼저 요청된 작업들을 큐에 삽입 

    while(index < jobs.length && jobs[index][0] <= currentTime){
        pq.offer(jobs[index]);
        index++;
    }

job 배열의 인덱스가 job의 길이보다 작고,

job 의 index번째의 첫번째 요소(요청 시간)이 현재 시간보다 작거나 같을 때 

큐에 넣어주고 index 올림

 

3) 큐가 비어있으면 현재 시간이 다음 작업 시간으로 이동하고,

큐에 요소가 있을 때 (실행 가능한 작업이 있을 때) 

맨 위의 요소를 꺼내서 현재 시간을 갱신하고, 요청부터 종료까지 걸린 시간을 구해서 더해준다.

그리고 작업 완료의 표시로 count를 더해준다.

if(pq.isEmpty()){
    //큐가 비어있으면 다음 작업 시간으로 이동
    currentTime = jobs[index][0];
}else {
    //실행 가능한 작업 중 소요 시간이 가장 짧은 작업 실행
    int tmpJob[] = pq.poll();
    //{ 요청시간, 작업시간 }

    //현재 시간 갱신
    currentTime += tmpJob[1];
    //요청부터 종료까지 걸린 시간
    totalWaitTime += currentTime - tmpJob[0];

    count++;
}

 

4. 평균 시간 구하기 

 answer = totalWaitTime / jobs.length;