[프로그래머스 LV3] 디스크 컨트롤러(Heap, 힙)

🧐 프로그래머스 LV3. 디스크 컨트롤러

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

- jobs의 길이는 1 이상 500 이하입니다.
- jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
- 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
- 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

jobs	return
[[0, 3], [1, 9], [2, 6]]	9

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

프로그래머스

 

💡 문제 풀이

우선순위 큐(Priority Queue)를 사용하는 문제였다. 처리 가능한 요청 중에서 작업 소요 시간이 짧은 요청을 기준으로 큐에 넣었다 빼고를 반복하니 계속해서 시간초과가 났다. 찾아보니 요청 시점을 기준으로 먼저 배열을 정렬하고, 처리 가능한 요청들을 하나씩 큐에 삽입해주는 방법으로 풀 수 있었다.

 

먼저 필요한 자료구조를 정의 및 초기화한다.

// 요청 시점을 기준으로 정렬
Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); 

// 소요 시간을 기준으로 우선순위 큐 초기화
Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); 

int count = 0; // 처리한 요청 수
int index = 0; // 큐에 삽입한 jobs 배열 인덱스 위치 저장
int time = 0; // 현시점
int answer = 0; // 처리한 요청에 대해서 (현시점 - 요청 시점) 값의 합

 

요청을 하나씩 판단해서 현시점에 가능한 요청부터 큐에 삽입하고, 그 중 소요시간이 짧은 요청부터 처리한다.

이 과정을 모든 요청이 처리될 때까지 반복한다.

while(count < jobs.length) {
	// 처리 가능한 요청 추가
	while (index < jobs.length && jobs[index][0] <= time) {
		pq.add(jobs[index++]);
	}
            
	if (pq.isEmpty()) time = jobs[index][0]; // 현시점 업데이트
	else { // 처리 가능한 요청이 있을 때
		int[] job = pq.poll(); // 소요시간이 가장 짧은 요청부터 처리
		time += job[1]; // 현시점 업데이트
		answer += time - job[0]; // 요청 처리 시간 업데이트
		count++; // 요청 처리 수 증가
	}
}

큐에 삽입하지 않은 요청(index < jobs.length)이고, 현시점에 처리 가능한 요청(jobs[index][0] <= time)이면 큐에 삽입한다.

이제 큐에서 소요시간이 가장 짧은 요청 하나를 꺼내서 처리한다.

하지만 큐가 비어있다면, 아직 요청을 처리할 수 있는 시점이 아니므로, 요청 시점이 가장 최근인 값으로 현 시점을 업데이트한다.

큐가 비어있지 않다면, 즉 처리 가능한 요청이 있다면, 하나 꺼내서 소요시간만큼 현시점을 업데이트 해주고, 해당 요청의 처리 시간도 업데이트, 요청을 하나 처리했으므로 요청 처리 수 값도 1만큼 업데이트한다.

 

위 과정이 끝난 후, 모든 요청 처리 시간의 합의 평균 값을 구하면 된다.

이 방식을 전체 코드로 풀어내면 다음과 같다.

 

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]); // 요청 기준 정렬
        Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); // 소요시간 기준
        int count = 0, index = 0, time = 0, answer = 0;

        while(count < jobs.length) {
            while (index < jobs.length && jobs[index][0] <= time) {
                pq.add(jobs[index++]);
            }
            
            if (pq.isEmpty()) time = jobs[index][0];
            else {
                int[] job = pq.poll();
                time += job[1];
                answer += time - job[0];
                count++;
            }
        }
        
        return (int) Math.floor(answer / jobs.length);
    }
}

 

✨ 포스팅을 마치며

요청 시점을 기준으로 먼저 정렬하는 방법을 찾아내지 못했다. 이 방법만 잘 떠올렸으면 나머지는 무난하게 풀어냈을 것 같다.