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

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

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

 

힙큐를 이용한 풀이법.

 

변수 설명

jobs 배열 -> { 들어온 시간, 처리되는 시간 }

 

풀이법 

 

하나의 처리가 종료되어야 다음 처리가 가능하기 때문에

큐를 이용해 들어온 처리들을 큐에 넣고 하나씩 꺼내면서 처리를 수행한다.

 

큐에서 꺼내어 처리 할 때마다 종료시간을 계산한다.

 

 

큐에 넣는 조건

현재 처리중인 노드의 종료시간을 계산.

종료시간보다 같거나 작은 시간에 들어온 노드들을 큐에 저장.

단 큐에 저장될 때 처리 시간이 낮은 순서로 저장한다.

위 조건대로 처리해야 가장 짧은 시간의 평균으로 구할 수 있다.

 

 

여기서 핵심은 정렬을 잘 이용하는 것!

 

처음 주어진 jobs 배열을 우선 들어온 시간순으로 정렬를 해준다.

 

public int solution(int[][] jobs) {
        int count = 0;
        int answer = 0;
        Arrays.sort(jobs, (o1,o2) -> o1[0]-o2[0]);
        //..생략

 

Arrays.sort 매서드를 이용하면 쉽게 정렬이 가능하다.

 

 

sort의 첫번째 인자는 정렬할 배열, 두번째 인자는 정렬할 조건을 넣어주면 해당 조건에 맞게 정렬이 가능하다.

두번째 인자는 Comparator 객체를 넣어준다.

람다식으로 Comparator 객체를 익명클래스로 넣어 줄 수 있다.

 

 

그 이후 jobs 를 처리할 Queue를 정의해 준다.

여기서 사용될 큐는 우선순위큐! ( 힙 구조로 되어있는 큐이다. )

(큐에 저장될 때 처리 시간이 낮은 순서로 저장한다.)

 

PriorityQueue<int[]> pqueue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

 

 

 

우선순위큐(PriorityQueue) 도 생성자 인자로 Comparator 객체를 받는다.

주입받은 Comparator 의 compareTo 메서드를 기준으로 큐를 정렬한다.

여기서도 람다식을 이용하여 익명클래스로 주입하였다.

 

이후 큐에서 데이터를 추출하면서 추출한 값이 jobs의 길이와 같아질 때 까지 반복하면서 시간을 계산한다.

 

 

        int curIdx = 0;
        int endTime = 0;
        while(count < jobs.length){

            while(curIdx < jobs.length &&  jobs[curIdx][0] <= endTime){ // 3.
                pqueue.add(jobs[curIdx++]);
            }
            if (pqueue.isEmpty()) { // 1.
                endTime = jobs[curIdx][0];
            }else{ // 2.
                int[] temp = pqueue.poll();
                answer += temp[1] + endTime - temp[0];
                endTime += temp[1];
                count++;
            }
        }

 

1. 큐가 비어있을 때

 

1) 첫번째 인자로 시작할 때

2) 모든 큐를 처리한 후 다음을 처리할 때

 

2. 큐에 들어있는 값들을 처리

 

answer => 현재 처리되는 노드가 들어온 순간부터 끝날때 까지 걸린 시간.

endTime => 현재 job이 끝나는 시간(다음 job 시작되는 시간)

 

3. 큐에 데이터 저장하기

 

아직 처리되지 않은 작업이 있고, (인덱스가 마지막까지 안갔음)

종료시간보다 이전에 들어온 모든 작업을 큐에 저장.

 

 

 

관점!

첫번째 루프가 count < jobs.length 인 이유

-> 카운트는 처리된 작업의 갯수를 의미함.

큐에 있는 모든 작업이 처리되어도 아직 들어오지 못한 인덱스가 존재할 수 있다.

 

ex) 입력값 [ [ 0,3 ], [ 1,1 ], [ 5,2 ] ] 인 경우

0,1 노드가 모두 처리되어도 3번 노드가 아직 안들어옴.

 

마지막으로 계산된 처리 시간을 전체 갯수로 나누어 준 후 나머지를 버려주면 정답!

 

 

전체 코드

 

 

class Solution42627{
    public static int solution(int[][] jobs) {
        int count = 0;
        int answer = 0;
        Arrays.sort(jobs, (o1, o2) -> o1[0]-o2[0]);

        PriorityQueue<int[]> pqueue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        int curIdx = 0;
        int endTime = 0;
        while(count < jobs.length){

            while(curIdx < jobs.length &&  jobs[curIdx][0] <= endTime){
                pqueue.add(jobs[curIdx++]);
            }
            if (pqueue.isEmpty()) {
                endTime = jobs[curIdx][0];
            }else{
                int[] temp = pqueue.poll();
                answer += temp[1] + endTime - temp[0];
                endTime += temp[1];
                count++;
            }
        }
        return (int) Math.floor(answer / jobs.length);
    }
}