문제 이해
- 요청이 들어오는 시점에, 작업 소요 시간도 알고 있음
- 한 번에 하나의 요청 만 수행 → 그러다보니, 요청이 들어오는대로 즉시 실행은 불가능함.
각 작업의 “요청 ~ 종료”까지 걸린 시간의 평균을 가장 많이 줄이는 방법으로 처리하면 평균이 얼마나 될까?
문제에서는 평균 turnaround time 의 최소값을 얻는 방법으로 처리하였을 때 그 결과가 얼마인지를 묻고 있다.
- 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 들어온 요청부터 처리
문제 풀이
( 다른 사람 풀이까지해서 거의 3시간 30분..ㅠㅠ)
- 문제조건
- job의 개수 → 500개
- 각 작업의 “요청”되는 시간 : 1000이하
- 각 작업 소요시간 : 1000이하
- SJF 는 average waiting time이 최소인 알고리즘. .starvation이 있더라도 SJF를 시도해볼까?
- 우선순위를 뭐로 해야할까..
그냥 SJF를 해보자
주어지는 정보의 형태 : ( 요청시간, 작업시간 )
Priority Queue에 넣는다. ( 우선순위 : “작업시간” - 짧을 수록 우선순위가 높도록 → minHeap )
어떤 task를 s ~ s +t 시간까지 실행한다면
- 이 사이에 오는 요청들을 Priority Queue에 넣어줘야한다.
- jobs가 오름차순으로 주어지나?? → 조건상으로는 그렇게 주어지지는 않았음..
어떤 작업의 turnaround time : 현재시간 - 요청 시간 + 작업시간
틀렸다
- SJF ( 들어와있는 요청 중 가장 짧은 요청 부터 실행 ) 은 맞다
- visit을 사용할 필요가 없었다
- jobs를 있는 그대로 사용하려고 한게 문제였다.
- jobs를 jobs[i][0](요청시간)을 기준으로 오름차순 정렬하면 , 배열 내에서 움직이면 되고, 같은 시간에 요청한 작업들은 → 어차피 q에 들어가면 “처리순으로 정렬”된다.
- 따라서 Arrays를 sorting할 때부터 , “처리시간”까지 정렬 기준에 넣어줄 필요없다.
다른 사람 풀이 보기
엄청 깔끔한듯
- end = 0 에서 시작한다. 정렬되어있는 jobs 에 idx를 하나 둔다 : jobIdx → 다음번에 q에 넣을 job의 위치를 추적한다.
- 이렇게 한다면, 요청시간 ≤ end인 job 들을 q 에 넣는 과정을 하기 수월 해 진다.
while(jobs[jobIdx][0] <= end)
pq.add( jobs[jobIdx++]);- 위의 과정 이후에도 pq가 비어있다면 ?? → end를 늘려줘야 한다 → 다음 end는 누구여야할까? → 요청시간이 현재end 이하인 작업들은 이미 q에 들어가있는 상태이기 때문에, 다음 jobIdx 위치의 job의 요청시간으로 end를 업데이트하도록 한다. ( jobIdx가 jobs의 length를 벗어나는 경우는 없는가?? → 작성자분의 코드처럼 count 까지 같이 세고 있는 상황이라면 그럴 일이 없다. count 가 아직 끝에 도달하지도 않았는데 q가 비어있다는 것은, 아직 q에 넣을 jobIdx가 존재한다는 것이니까 )
- pq 에 원소가 들어있다면, pq에서 원소를 뽑아낸다 → 작업 하나를 수행한다.
- sum 을 업데이트 한다 ( end는 현재시간 이기 때문에 → 이 작업의 요청~끝날때까지 시간 : end - task[0] + task[1] 이 된다 )
- end를 업데이트한다.
- 수행한 작업의 개수를 count 해 준다.
import java.util.*;
class Solution {
// Ready queue 는 처리시간 기준으로만 minHeap
public static PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1]-o2[1];
}
});
// SJF 라면?
public int solution(int[][] jobs) {
int answer = 0;
int count = 0, end = 0, jobIdx = 0, sum = 0 , len = jobs.length;
int[] task = null; // pq 에서 꺼낸 작업 ( 현재처리할 작업)
// 요청시간을 기준으로 오름차순 정렬
Arrays.sort(jobs,(o1,o2)->{
return o1[0]-o2[0];
});
// count 는 처리한 요청의 개수
while(count<len){
// 요청시간 <= end 인 job들을 q 에 넣는다 (이 때 jobIdx 의 범위에 주의)
while(jobIdx<len && jobs[jobIdx][0]<=end){
q.add(jobs[jobIdx++]);
}
// 그래도 pq가 비어있으면 end를 업데이트한다
if(q.isEmpty()) end = jobs[jobIdx][0];
else{
// 작업을 하나 처리한다
task = q.poll();
sum += (end - task[0] + task[1]);
end += task[1];
count++;
}
}
answer = sum/len;
return answer;
}
}