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

문제보러가기

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

이문제는 작업 수행 시 어떤 순서로 진행을 해야 하는가를 계산하는 문제이다. 작업할 수 있는 시간에 요청이 들어와 있는 작업 중 수행 시간이 짧은 작업을 선택하여 먼저 실행하면 되는 문제였다. 처음에는 간단하다고 생각했는데 문제를 잘 읽어봐야 한다 역시... 요청 시간 순으로 jobs배열이 구성된다는 내용은 어디에도 없었다 ㅎ,, 

 

 

문제풀이

-모든 작업을 수행할 때까지 cnt 카운트를 진행한다.

-time은 계속 흘러가고 time==jobs [i][0](요청 시간) 일 경우 우선순위 큐에 저장한다.

-큐에는 요청 시 간과 수행 시간이 쌍으로 담긴 Task 클래스를 만들어 저장한다.

-우선순위 큐의 정렬 방식: 작업을 처리할 수 있는 것만 들어왔으므로(time==jobs [i][0](요청 시간) 이 과정을 통해) 수행 시간이 적은 것을 우선으로 정렬한다. 만약 같을 경우 요청이 먼저 들어온 것을 우선으로 정렬한다.

 

※ 내가 헤맸던 부분은 jobs배열이 요청 순서대로 정렬되어있지 않다는 점과, 같은 시간에 여러 개의 요청이 들어올 수 있다는 점! 나는 이 부분을 while 문을 돌 때마다 해당하는 jobs배열 요소 모두를 큐에 넣을 수 있게 for문을 사용했다. 시간 초과가 날까 했지만 통과!

 

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class DiskController {

	public static void main(String[] args) {

		int[][] jobs = { { 0, 9 }, { 0, 4 }, { 0, 5 },{0,7} ,{0,3}};//testcase 답:13

		int time = 0;
		int answer = 0;
		int finishT = 0;
		int cnt = 0;
		PriorityQueue<Task> minHeap = new PriorityQueue<>();

		//모든 작업이 수행될 수 있도록 cnt
		while (cnt < jobs.length) {
        	//해당타임에 요청한 작업 모두 큐에 저장
			for(int i=0;i<jobs.length;i++){
				if (time == jobs[i][0]) {
					minHeap.add(new Task(jobs[i][0], jobs[i][1]));
				}
			}
            //time이 작업이 끝난 이후고 큐에 작업요청이 있다면
            //answer,작업이끝날시간(finishT) 갱신
			if ((time >= finishT) && !minHeap.isEmpty()) {
				Task task = minHeap.poll();
				answer += time - task.start + task.executeT;
				finishT = time + task.executeT;
				cnt++;
			}
			time++;
		}
		System.out.println(answer / jobs.length);
	}

}
//정렬기준 정해주기
class Task implements Comparable<Task> {
	int start;
	int executeT;

	Task(int start, int executeT) {
		this.start = start;
		this.executeT = executeT;
	}
	//수행시간 오름차순으로, 같을경우 요청시간 오름차순으로
	@Override
	public int compareTo(Task t) {
		if (this.executeT < t.executeT)
			return -1; // 오름차순
		else if (this.executeT == t.executeT) {
			if (this.start < t.start)
				return -1;
		}
		return 1;
	}
}