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

---

프로그래머스 Lv3 - 디스크 컨트롤러 문제

프로그래머스 알고리즘 고득점 Kit 카테고리의 힙 문제 중 레벨 3 디스크 컨트롤러 문제를 풀이했다.

힙 자료구조로 구현한 자바의 우선순위 큐 클래스를 통해 풀이하였다.
역시 3단계인가 문제 풀이 과정에 어려움들을 겪었다. 무엇보다 왜 틀렸는지 반례 케이스가 없어서 프로그래머스의 질문하기 항목에 들어가서 사람들이 적어놓은 반례 케이스들을 테스트 케이스에 추가해 문제를 풀이했다.

내가 반례 케이스를 추가하고 찾아낸 풀이 중 놓쳤던 부분은 한 가지로
1. 같은 시점에 요청하는 작업이 있을 수 있다. -> 같은 시점의 경우 작업 소요 시간이 짧은 순으로 처리해야 함

이 부분을 우선순위큐를 두 개로 나누는 방법으로 처리했다.

requestPq에 요청 시간이 작은 순으로 삽입 후, progressPq에 삽입할 때는 requestPq에서 요청 시간이 작은 순으로 방출되는 Job객체를 작업 소요 시간이 작은 순으로 삽입 후 후처리를 하게 된다.

지난 포스팅에서 공부한 Comparator<E> 인터페이스를 활용하여 풀어서 뿌듯하다~!

DiskController.java

package com.example.Programmers.Lv3;

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

/**
 * 프로그래머스 Lv3 - 디스크 컨트롤러
 * Heap문제 우선순위 큐 활용 풀이
 */
public class DiskController {
    public int solution(int[][] jobs) {
        int answer = 0;

        // 요청 시간 우선순위 큐 정렬 조건 설정(요청시간 오름차순)
        PriorityQueue<Job> requestPq = new PriorityQueue<>(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                return o1.getRequestTime() - o2.getRequestTime();
            }
        });
        // 소요 시간 우선순위 큐 정렬 조건 설정(소요시간 오름차순)
        PriorityQueue<Job> progressPq = new PriorityQueue<>(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                return o1.getProgressTime() - o2.getProgressTime();
            }
        });

        // 우선순위 큐 초기화
        for (int i = 0; i < jobs.length; i++) {
            requestPq.add(new Job(jobs[i][0], jobs[i][1]));
        }

        // 현재까지의 소요 시간 저장 변수
        int tick = 0;

        while (!requestPq.isEmpty() || !progressPq.isEmpty()) {
            // requestPq에서 뽑은 것이 tick이하인 job들만 뽑아서 progressPq에다가 넣기(현재 시점에 작업 가능한 job들)
            while (!requestPq.isEmpty()) {
                if (requestPq.peek().getRequestTime() <= tick) {
                    Job job = requestPq.poll();
                    progressPq.add(job);
                } else {
                    break;
                }
            }
            // 현재 tick이하인 job들이 들어 있는 progressPq에서 하나씩 뽑아 처리
            // 만약 현재 tick이하인 job이 없다면 시간 재조정
            if (progressPq.isEmpty()) {
                tick++;
            } else { // 현재 tick이하인 job이 있다면 처리 후 평균을 내기 위해 answer 변수에 합 연산 수행 및 현재 시점 재조정
                Job job = progressPq.poll();
                answer += tick + job.getTotalTime();
                tick += job.getProgressTime();
            }
        }
        answer /= jobs.length;
        return answer;
    }
}

class Job {
    private int requestTime;
    private int progressTime;
    private int totalTime;

    Job(int requestTime, int progressTime) {
        this.requestTime = requestTime;
        this.progressTime = progressTime;
        this.totalTime = progressTime - requestTime;
    }

    int getRequestTime() {
        return this.requestTime;
    }

    int getProgressTime() {
        return this.progressTime;
    }

    int getTotalTime() {
        return this.totalTime;
    }
}

DiskControllerTest.java

package com.example.Programmers.Lv3;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class DiskControllerTest {
    @Test
    public void testDiskController() {
        DiskController d = new DiskController();

        int result1 = d.solution(new int[][] { { 0, 3 }, { 1, 9 }, { 2, 6 } });
        int result2 = d.solution(new int[][] { { 0, 1 }, { 2, 2 }, { 2, 3 } });
        int result3 = d.solution(new int[][] { { 0, 3 }, { 2, 5 }, { 4, 2 } });

        assertEquals(9, result1);
        assertEquals(2, result2);
        assertEquals(5, result3);
    }
}