문제 출처
코딩테스트 연습 > 힙(Heap) > 디스크 컨트롤러
https://school.programmers.co.kr/learn/courses/30/lessons/42627
문제 설명
[요청 시점][소요 시간] 을 요소로 가진 2차원 배열 jobs가 주어진다.
하드디스크가 작업을 하지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내 하드디스크에게 작업을 시킨다.
우선순위의 기준은 소요시간이 가장 짧은 것, 요청 시점이 가장 빠른 것, 작업 고유 번호가 가장 낮은 것 순서이다.
이 때, 우선순위 디스크 컨트롤러가 모든 요청 작업을 처리했을 때, 반환 시간의 평균의 정수부분을 return 하라.
접근 방법
단계를 순차적으로 나눠보면
- 원본 배열을 오름차순 정렬한다.(요청시간 기준)
- 우선순위 큐를 소요시간 기준으로 오름차순 정렬한다.
- 요청이 모두 수행될 때까지 반복한다. 반복하는 내용은 다음과 같다.
3-1. 하나의 작업이 완료되는 시점까지 들어온 모든 작업 요청을 우선순위 큐에 삽입한다.
3-2. 만약 우선순위 큐가 비어있다면, 현재 완료된 작업의 종료 시점까지 작업이 요청 된 것이 없으므로 jobs의 다음 요소의 종료 시점으로 종료 시간을 맞춰준다.
3-3. 들어온 요청 중(우선순위 큐 안 작업) 수행시간이 짧은 순서대로 작업을 수행한다.
로 정리할 수 있다.
% 반환 시간 = 종료 시간 - 요청 시간
import java.util.*;
class Solution {
public int solution(int[][] jobs) {
int answer = 0;
// 원본 배열을 오름차순 정렬한다.(요청시간 기준)
Arrays.sort(jobs, (a,b) -> (a[0] - b[0]));
// 우선순위 큐를 소요시간 기준으로 오름차순 정렬한다.
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);
int count = 0;
int end = 0;
int jobsIndex = 0;
// 요청이 모두 수행될 때까지 반복한다.
while(count < jobs.length){
// 하나의 작업이 완료되는 시점까지 들어온 모든 작업 요청을 우선순위 큐에 삽입한다.
while(jobsIndex < jobs.length && jobs[jobsIndex][0] <= end){
pq.add(jobs[jobsIndex++]);
}
// 만약 우선순위 큐가 비어있다면, 현재 완료된 작업의 종료 시점까지 작업이 요청 된 것이 없으므로 jobs의 다음 요소의 종료 시점으로 종료 시간을 맞춰준다
if(pq.isEmpty()){
end = jobs[jobsIndex][0];
}
// 들어온 요청 중(우선순위 큐 안 작업) 수행시간이 짧은 순서대로 작업을 수행한다.
else{
int temp[] = pq.poll();
answer += temp[1] - temp[0] + end;
end += temp[1];
count++;
}
}
return answer/jobs.length;
}
}알게된 점
처음 문제를 접했을 땐, 문제에서 이용하라는 것이 너무 많았다.(ex -> 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장하는 대기 큐)
그래서 어떻게 접근해야하는지 모르겠어서 PriorityQueue에 소요시간만을 넣고 접근했다.
하지만 이는 jobs 배열에서 요청 시간, 인덱스 등 다시끔 가져와야하는 정보가 너무 많아서 결국 풀지 못했다.
참고 풀이
https://codevang.tistory.com/316
다른 풀이들을 확인해보니, 우선순위 큐에 1차원 배열(int[])를 삽입하여 소요시간, 작업시간을 모두 넣는 방식을 사용하면 깔끔하게 접근 할 수 있음을 알게 되었다.
아직 자바로 자료구조 사용하는 방법이나, 자료형에 대해 미숙한 것같다.
내일 다시 풀어봐야겠다.
% 나도 level 3 문제를 혼자서 풀어내고 싶다.
문제푼 흔적
