[Programmers] 코딩테스트 디스크 컨트롤러 JAVA

728x90

반응형

[Programmers] 디스크 컨트롤러

---

접근

• 우선순위 큐

---

풀이

문제의 내용은 비선점 스케줄링인 SJF, Shortest Job First 기법과 일치하다. 비선점으로 수행하던 작업이 끝날 때까지 대기하고 끝나고 나면 해당 시점에 대기 중인 프로세스 중 가장 수행 시간이 짧은 프로세스를 먼저 실행하는 기법이다. 선점 스케줄링 기법인 SRF, Shortest Remaining Time First 기법과는 다르게 수행 중인 프로세스를 건들지 않기에 더 간단하게 구현을 할 수 있을 것이다.

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

우선 입력받는 jobs를 작업 요청 시간 기준으로 정렬해 주었다.

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

이번 문제의 핵심인 우선순위 큐를 선언해 주었고 우선순위의 기준을 작업 시간으로 가지게 해 주었다. 이렇게 한다면 큐에 넣기만 하면 알아서 짧은 순서대로 실행을 해 줄 거 기 때문에 이미 절반은 푼 거나 다름이 없다.

int time = 0;
int index = 0;
int totalWaitTime = 0;
int completedJobs = 0;

각종 변수들이다. 현재 시간을 나타낼 time 변수, jobs 배열의 인덱스를 관리할 index, 변수 전체 대기 시간을 관리할 totalWaitTime 변수, 완료된 작업을 관리할 completedJobs 변수이다.

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

while 문 아래서 Jobs내 모든 작업이 완료될 때까지 반복한다. 현재 시간이 jobs 배열의 작업 요청 시간을 지나면 큐에 추가해 준다.

	if (pq.isEmpty()) {
		time = jobs[index][0];
	} else {
		int[] currentJob = pq.poll();
		time += currentJob[1]; 
		totalWaitTime += time - currentJob[0]; 
		completedJobs++; 
	}
}

큐가 비었다면 다음 작업을 위해 jobs 배열에서 새로운 작업의 요청 시간을 time에 할당해 준다. 큐가 비어있지 않다면 현재 작업을 처리한다. 현재 작업 수행에 걸리는 시간만큼 time을 늘려주고 총 대기 시간도 계산해 최신화해 준다. 그리고 작업을 하나 처리했기 때문에 처리한 작업의 수를 늘려준다.

return totalWaitTime / jobs.length;

반복문이 끝나게 되면 평균을 구하기 위해 총 대기 시간과 작업의 개수로 나누어 주면 답이 나온다.

---

전체 코드

import java.util.*;

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 time = 0;
        int index = 0;
        int totalWaitTime = 0;
        int completedJobs = 0;

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

            if (pq.isEmpty()) {
                time = jobs[index][0];
            } else {
                int[] currentJob = pq.poll();
                time += currentJob[1];
                totalWaitTime += time - currentJob[0];
                completedJobs++;
            }
        }

        return totalWaitTime / jobs.length;
    }
}

처음엔 while문을 사용해 반복 한 번당 1초로 두고 직접 실행을 통해 계산해 보려 했으나 크기가 조금만 커져도 매우 비효율적인 방법으로 그만두었다. 기본 내장된 우선순위 큐 라이브러리를 이용해 풀었지만 알고리즘 공부를 위해 문제를 풀려면 우선순위 큐 자체를 직접 구현해 푸는 것이 맞는 게 아닌가 싶긴 하다.