[Programmers] 디스크 컨트롤러

난이도 : Level 3

문제링크

• 하드디스크는 한번에 하나의 작업만 수행할 수 있습니다.
• 각 작업의 요청시간-소요시간을 담은 2차원 배열 jobs가 주어진다.
• 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리할 때의 평균값을 리턴하라

 

해설

출처에서 공부한 내용을 정리했습니다

1. 변수 선언하기

int cnt = 0;
int idx = 0;
int end = 0;

• cnt : 처리된 작업의 수
• idx : 현재 처리한 작업의 인덱스
• end : 현재 처리한 작업의 종료시간

 

2. 요청시간이 빠른 순으로 처리하고, 우선순위 큐로 다음 처리할 작업 정하기

Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

• 요청시간이 빠른 것부터 처리해야 뒤에 처리할 작업의 대기시간이 적습니다.
• 현재 처리하는 작업의 처리시간 내에 시작하는 작업이라면
  • 작업시간이 짧은것부터 처리해야 뒤에 처리할 작업의 대기시간이 적습니다.

 

3. 전체 작업 처리하기

while (cnt < jobCnt) {
    while (idx < jobCnt && jobs[idx][0] <= end) {
        pq.offer(jobs[idx++]);
    }

    if (pq.isEmpty()) {
        end = jobs[idx][0];
    } else {
        int[] tmp = pq.poll();
        answer += tmp[1] + end - tmp[0];
        end += tmp[1];
        cnt++;                
    }
}

• 현재 작업의 종료시간 내에 시작하는 작업 처리
  • 소요시간이 적은 작업을 먼저 처리하기 위해 우선순위 큐에 넣는다
  • 현재 작업의 종료시간과 전체 처리시간을 갱신하여 처리한다
• 종료시간 내에 처리할 작업이 없다면
  • 현재 작업의 종료시간을 갱신하여 현재 처리해야 할 작업을 큐에 넣는다

 

 

블로그 참고

• 코데방 - 프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA)