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

문제

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

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

 

해당 유형의 문제들을 코테에서 자주 접하게 된다.

항상 못풀었기에 이번엔 걍 배우는 마음으로 코드를 보기로

 

참고

velog.io/@sa833591/%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv.3

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

 

 

Heap 문제기 때문에 PriorityQueue를 사용하여 푼다.

1. 디스크 컨트롤러는 먼저 들어온 작업 순서대로 처리한다.
2. 1이 원칙이나, 대기 작업 중에서 작업이 완료되는 데 걸리는 시간이 가장 작은 작업을 우선적으로 처리한다.
3. 대기큐에 있던 작업 수행과 새 작업은 계산 방법이 조금 다르다.

 

문제에서 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하라는 힌트가 있다.

→ 다음 두 가지를 유추해낼 수 있어야 한다.

1. jobs 요청시간에 대해 오른차순 정렬을 한다. 단, 요청 시간이 동일한 경우 작업 시간에 따라 오름차순으로 정렬한다.
2. 작업 시간에 대해 오름차순 정렬되는 대기 큐(PriorityQueue)를 생성한다.

 

velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC-Java

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

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

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

 

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

 

코드

import java.util.*;

class Main {
    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<Job>(new Comparator<Job>() {
    		@Override
    		public int compare(Job j1, Job j2) {
    			return j1.workingTime - j2.workingTime;
    			// 음수 (j1.workingTime < j2.workingTime)
    			// 0 (j1.workingTime == j2.workingTime)
    			// 양수 (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;
    }
    public static void main(String[] args) {
    	Main s = new Main();
    	int[][] jobs = {{0,3},{1,9},{2,6}};
    	
    	System.out.println(s.solution(jobs));
    }
}