[프로그래머스] 디스크 컨트롤러 (Java)

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

문제풀이

이 문제는 스케쥴링 알고리즘 중 하나인 SJF 알고리즘을 구현하는 문제였다.

• SPN(Shortest Process Next) / SJF(Shortest Job First)
  • 준비 큐에서 가장 짧은(CPU 요구량이 가장 적은) 프로세스에게 CPU 할당.
  • starvation 발생가능, aging 기법으로 해결
  • 실행 전에는 실행 시간을 알 수 없다. 지수 평균 방법을 통해 추측한다.

원래는 실행 전에는 실행 시간(작업 시간)을 알 수 없지만 이 문제에서는 미리 주어지기 때문에 신경쓸 필요가 없다. 어렵지 않은 문제이나 이상한 곳에 꽂혀서 시간을 엄청나게 허비했다.

• 대기 큐에 모든 작업을 넣고 요청 시간을 기준으로 오름차순 정렬한다.
• 모든 작업이 완료될 때 까지 다음을 반복한다.
  • 현재 시간 이하의 요청시간을 가지는 작업을 모두 대기큐에서 작업 큐로 옮긴다.
  • 작업 큐에서 가장 작업시간이 짧은 작업을 꺼내어 작업한다.
    • 작업 큐는 작업시간을 기준으로 오름차순 정렬되어있다.
    • 현재 시간에 현재 작업의 작업시간을 더해준다.
    • Turn Arround Time의 평균 시간을 구하기 위해서 각 작업의 Turn Arround Time을 answer에 더해나간다.
    • 완료된 작업의 숫자인 cnt를 +1 한다.
  • 작업 큐가 비어있는 경우 현재 시간을 +1 한다.

구현코드

import java.util.*;

class Solution {
    class Job {
        int requestTime;
        int workingTime;
        
        Job(int requestTime, int workingTime){
            this.requestTime = requestTime;
            this.workingTime = workingTime;
        }
    }
    
    public int solution(int[][] jobs) {
    	LinkedList<Job> waiting = new LinkedList<>();
    	PriorityQueue<Job> pq = new PriorityQueue<>(new Comparator<Job>() {
    		@Override
    		public int compare(Job j1, Job j2) {
    			return j1.workingTime - j2.workingTime;
    		}
    	});
    	
    	for(int[] job : jobs) {
    		waiting.offer(new Job(job[0], job[1]));
    	}
    	
    	Collections.sort(waiting, new Comparator<Job>() {
			@Override
			public int compare(Job j1, Job j2) {
				return j1.requestTime - j2.requestTime;
			}
    	});
    	
    	int answer = 0;
    	int cnt = 0;
    	int time = waiting.peek().requestTime;

    	while(cnt < jobs.length) {
    		while(!waiting.isEmpty() && waiting.peek().requestTime <= time) {
    			pq.offer(waiting.pollFirst());
    		}
    		
    		if(!pq.isEmpty()) {
    			Job job = pq.poll();
    			time += job.workingTime;
    			answer += time - job.requestTime;
    			cnt++;
    		} else {
    			time++;
    		}
    	}
    	
    	return answer / cnt;
    }
}