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

1. 문제 파악

하드디스크는 한 번에 하나의 작업만 수행할 수 있다. 이를 구현하는 문제가 된다.

2차원 배열은 [작업이 요청되는 시점, 작업의 소요시간]으로 구분이 된다고 한다.

그렇다면 작업을 요청한 순서대로 처리한다면 어떻게 될까?

작업을 요청한 순서대로 처리

o 일때만 작업을 처리하는 것이다. 나머지는 대기시간이고 평균 시간을 구하면 (3+11+16) / 3 = 10이 나온다.

 

반면 작업의 소요시간 순으로 처리한다면 어떻게 될까?

작업의 소요시간 순서대로 처리

평균시간을 구하면 (3+7+17) / 3 = 9가 나온다.

즉, 작업의 소요시간대로 처리하면 된다. 작업의 소요시간을 기준으로 오름차순 정렬하고 하나씩 꺼내 쓰면 된다.

하지만 작업 중인데 그때 요청되는 경우도 존재한다.

그러므로 작업을 요청한 순서도 정렬을 해야한다. 그래야 총 소요시간을 구할 수 있다.

이번에도 우선순위 큐를 사용해서 문제를 해결했다.

2. 구현

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int time = 0;
        //요청 시간 순 정렬
        Arrays.sort(jobs,Comparator.comparingInt(o -> o[0]));
        //소요 시간 순 정렬
        PriorityQueue<int[]>p = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        
        //처리 순서
        int wait = 0;
        //처리 끝난 후 시간
        int end = 0;
        //처리된 작업
        int finishJob = 0;
        
        //작업을 전부 완수할때 까지!
        while(jobs.length > finishJob){
            //남은 작업이 존재하면서 현재 종료시간보다 요청시간이 빠르면?
            while(wait < jobs.length && end >= jobs[wait][0]){
                //작업을 추가
                p.offer(jobs[wait++]);
            }
            //만약 요청이 없으면? 초기 값을 잡아준다.
            if(p.isEmpty()){
                end = jobs[wait][0];
            }
            //처리
            else{
                //처리
                int[] job = p.poll();
                //작업시간 + 작업이 종료된 시점 - 요청시간
                time += job[1] + end - job[0];
                //현재까지 처리된 수
                end += job[1];
                //다음 작업
                finishJob++;
            }  
        }
        answer = time / jobs.length;
        return answer;
    }
}

먼저 2차원 배열을 요청시간을 기준으로 정렬했다. 우선순위 큐는 앞서 말한 것 처럼 소요시간 기준으로 정렬했다.

처리 못한 작업이 존재하고 그 작업이 바로 처리를 못해준다면 일단 큐에 넣어주었다.

다음으로 처리를 할 때 time을 구하는 방법이 이해가 가지 않아 그림을 그리면서 해결했다.

만약 처음 작업을 처리하고 2번째를 처리할려고 한다.

현재 시간은 3초를 지나고 있고 요청은 2초에서 들어왔다. 그리고 작업을 처리하는데는 총 6초가 걸린다.

우리가 구해야하는 건 2번 인덱스를 처리할 때 소요되는 시간이다.

그렇다면 작업의 소요시간 + 작업 대기시간이 된다. 작업 대기시간은 풀어쓰면 현재시간 - 작업 요청시간이 된다.

그러므로 작업의 소요시간 + 현재시간 - 작업 요청시간이 된다.

3. 마무리

작업마다 처리시간을 계속 잘못이해해서 시간이 조금 걸린 문제였다.

그리고 요청시간이 보기에는 0, 1, 2 순이라 정렬이 된 상태인줄 알았지만 내가 정렬을 해줘야한다..

Comparator.comparingInt(o -> o[정렬할 요소(0이면 열 기준, 1이면 행기준(2차원 배열 기준)])을 처음 써봤는데 생각보다 유용해서 외워야 겠다.