알고리즘/프로그래머스
[프로그래머스] 디스크 컨트롤러 Java 풀이 및 해설
승민아
2024. 5. 18. 12:16
https://school.programmers.co.kr/learn/courses/30/lessons/42627#
풀이 방법
- 수행할 작업 목록을 요청 시각 오름차순으로 정렬한다.
- 우선순위 큐 선언한다. 소요 시간이 작은것이 먼저 뽑아져 나온다.
- X, Y 두개의 작업을 수행할 수 있을때 X 작업을 끝내는데 a 시간이 걸리고 Y 작업을 끝내는데 b 시간이 걸린다고하자
- 두개의 작업 앞에 c 시간이 걸린다면
- X -> Y 순으로 작업을 한다면 각 작업을 끝내는데 걸리는 시간은
- X : c + a, Y : c + c + a + b 이다.
- 만약 X가 오래 걸리는 작업이고 Y는 짧은 작업이라면 Y는 X 때문에 작업을 끝내는데 걸리는 시간이 늘어난다.
- 즉, 짧게 걸리는 작업을 우선으로 작업하는것이 각 작업을 끝내는데 걸리는 시간이 최소가 된다.
- 정렬된 작업 목록에서 작업 하나를 뽑아온다.
- 이 작업을 끝내는동안 들어올 수 있는 작업들을 우선순위 큐에 넣는다.
- 우선순위 큐에서 작업을 뽑아 온다.
- 이 작업을 끝내는동안 들어 올 수 있는 작업들을 우선순위 큐에 넣는다.
- 우선순위 큐가 빌때까지 5 -> 6 과정을 반복한다.
전체 코드
import java.util.*;
class Solution {
class Job {
int requestTime; // 요청 시각
int needTime; // 소요 시간
public Job(int requestTime, int needTime) {
this.requestTime = requestTime;
this.needTime = needTime;
}
}
public int solution(int[][] jobs) {
int answer = 0; // 각 작업이 요청부터 종료까지 걸린 시간 (아직 평균은 안냈음)
// 요청 오름차순
Arrays.sort(jobs, (o1, o2) -> {
if(o1[0] == o2[0])
return o1[1] - o2[1];
return o1[0] - o2[0];
});
// 우선순위 큐 : 소요시간이 작은게 먼저 나옴. 수행해야할 작업 목록
PriorityQueue<Job> pq = new PriorityQueue<>((o1, o2) -> {
return o1.needTime - o2.needTime;
});
// 수행할 작업
int idx = 0;
while(idx < jobs.length) {
pq.add(new Job(jobs[idx][0], jobs[idx][1])); // 첫번째 작업 수행
int curTime = jobs[idx][0]; // 현재 시각
// 첫번째 작업을 수행하며 들어온 작업들 확인
idx++;
while(pq.size() != 0) {
Job job = pq.poll();
answer += (job.needTime + curTime) - job.requestTime; // 작업 처리 시간
curTime += job.needTime; // 현재 시간은 작업 소요 시간을 더해줌
// 현재 시간 이내 다른 작업이 들어올 수 있는지 확인
while(idx < jobs.length && jobs[idx][0] <= curTime) {
pq.add(new Job(jobs[idx][0], jobs[idx][1]));
idx++;
}
}
}
answer /= jobs.length;
return answer;
}
}