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

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

코딩테스트 연습 - 디스크 컨트롤러

import java.util.PriorityQueue;
class Solution {
		 class Info{
			int arrive, burst;
			public Info(int arrive, int burst) {
				this.arrive = arrive;
				this.burst = burst;
			}
		}
	    public int solution(int[][] jobs) {
	        int answer = 0;
	        
	        PriorityQueue<Info> total = new PriorityQueue<>((o1,o2) -> (o1.arrive-o2.arrive));
	        PriorityQueue<Info> wait = new PriorityQueue<>((o1,o2) -> (o1.burst-o2.burst));
	        
	        for(int i=0; i<jobs.length; i++) {
	        	int arrive=jobs[i][0];
	        	int burst=jobs[i][1];
	        	total.add(new Info(arrive,burst));
	        }
	        int time=total.peek().arrive;
	        
	        while(true) {
	        	//현재 time 안에 들어와있는 작업들 모두 wait큐에 넣어주기
	        	while(!total.isEmpty()) {
	        		Info info=total.poll();
	        		if(info.arrive<=time) wait.add(info);
	        		else {
	        			total.add(info);
	        			break;
	        		}
	        	}
	        	
	        	if(wait.isEmpty() && total.isEmpty()) break;
	        	if(wait.isEmpty() && !total.isEmpty()) {
	        		Info curWork=total.poll();
	        		time=curWork.arrive+curWork.burst;
	        		answer+=curWork.burst;
	        		continue;
	        	}
	        	
	        	Info curWork=wait.poll();
	        	time+=curWork.burst;
	        	answer+=(time-curWork.arrive);
	        }
	        return answer/jobs.length;
	    }
	}

소요시간 : 30분

 

SJF에 대한 개념이 있다면 쉽게 풀 수 있는 문제입니다! 

(작업이 끝나는 대기 큐의 작업 중 가장 CPU burst가 작은 작업을 먼저 실행!)

 

우선 우선순위 큐를 2개 만들었습니다

하나는 전체 작업을 저장할 total (도착시간 오름차순)

하나는 대기 큐의 역할을 해줄 wiat (cpu burst 오름차순)

 

로직은 간단합니다!

현재 시간보다 작거나 같다면 total 큐에서 wait큐로 옮겨줍니다! 

그리고 wait큐중 가장 cpu burst가 작은 작업을 꺼내서 time 과 요청부터 걸린시간을 갱신해주면 됩니다!

 

한가지 예외사항이 있다면 

{0,3}
{15,5} 이런식으로 중간에 텀이 있는 테스트케이스입니다.

 

그래서 만약 total큐가 비어있지 않은데 wait큐가 비어있는 경우를 따로 확인해서 처리했습니다!