[JAVA] 힙 "디스크 컨트롤러"

이 문제는 2가지를 고려하여 코드를 짜야한다.

 

1. '작업소요시간'이 짧은 작업부터 수행해야한다.

2. 단, 하나의 작업이 끝나는 시점을 기준으로, '그 이전까지 요청된' 작업들에 한하여 '작업소요시간'을 비교한다.

 

필자는 런타임에러로 인해 코드작성에 실패하여, 다른사람의 코드를 리뷰하겠다.

첫번째는, 람다식을 이용하여 풀이를 하는 방식이다.

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

class Solution {

	public int solution(int[][] jobs) {

		int answer = 0;
		int end = 0; // 수행되고난 직후의 시간
		int jobsIdx = 0; // jobs 배열의 인덱스
		int count = 0; // 수행된 요청 갯수

		// 원본 배열 오름차순 정렬 (요청시간 오름차순)
		Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);

		// 처리 시간 오름차순으로 정렬되는 우선순위 큐(Heap)
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

		// 요청이 모두 수행될 때까지 반복
		while (count < jobs.length) {

			// 하나의 작업이 완료되는 시점(end)까지 들어온 모든 요청을 큐에 넣음
			while (jobsIdx < jobs.length && jobs[jobsIdx][0] <= end) {
				pq.add(jobs[jobsIdx++]);
			}

			// 큐가 비어있다면 작업 완료(end) 이후에 다시 요청이 들어온다는 의미
			// (end를 요청의 가장 처음으로 맞춰줌)
			if (pq.isEmpty()) {
				end = jobs[jobsIdx][0];

			// 작업이 끝나기 전(end 이전) 들어온 요청 중 가장 수행시간이 짧은 요청부터 수행
			} else {

				int[] temp = pq.poll();
				answer += temp[1] + end - temp[0];
				end += temp[1];
				count++;
			}
		}

		return (int) Math.floor(answer / jobs.length);
	}
}

우선순위 큐에 비교자를 저러게 int[]배열로 받을 수 있다. 위와같이 받을경우,

jobs[0] 배열int[]에 들어 있는 것들	jobs[1] 배열int[]에 들어있는 것들	jobs[2] 배열int[]에 들어있는 것들
jobs[0][0]	jobs[1][0]	jobs[2][0]
jobs[0][1]	jobs[1][1]	jobs[2][1]

따라서 ELSE문의 temp[0] temp[1]값도 priorityQueue에서 poll()한값이 위의 값과 같다.

이러한 방식으로 2차원 배열의 각각의 원소를 1차원으로 저장하는 방식을 익혀두어야겠다.

 

참고로 Math.floor(값)는 반올림해주는 메소드라고 한다.

 

 

다음은, 두번째 방식 코드리뷰이다. 이 방식은 위의 방식과 비교해 볼 필요가 있다.

import java.util.*;
class Solution {
public static int solution(int[][] jobs) {

      Arrays.sort(jobs, new Comparator<int[]>() {
          public int compare(int[] o1, int[] o2) {
              if(o1[0] <= o2[0]){
                  return -1;
              }
              return 1;
          }
      });      

      PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
          public int compare(int[] o1, int[] o2) {
              if(o1[1] < o2[1]){
                  return -1;
              }
              return 1;
          }
      });

      int time = 0;
      int index = 0;
      float answer = 0;

      while(true){
          while(index < jobs.length && jobs[index][0] <= time){
              queue.offer(jobs[index]);
              index ++;
          }
          if(queue.size() == 0){
              time = jobs[index][0];
              continue;
          }
          int[] job = queue.poll();
          time += job[1];
          answer += time - job[0];
          if(index == jobs.length && queue.size() == 0){
              break;
          }
      }

      answer /= jobs.length;
      return (int)answer;
    }
}

 해당 코드는 기존의 객체 선언 방식이고, 첫번째 코드는 람다식을 이용한 방식이다.

람다식을 이용하면 훨씬 간결하게 해결 할 수 있음을 다시한번 느낄 수 있다.