디스크 컨트롤러

작성일: 2024-10-28

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42627

접근 방식

주어진 2차원 배열에는 요청 시작 시점과, 처리 시간이 담겨있다.

시작 시점을 기준으로 처리하는 경우, 최소 소요 시간을 보장하지 않는다.

따라서, 시작 시점 + 처리 시간을 기준으로 정렬해서, 구하고자 했다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, Comparator.comparingInt(a->a[1]));
        int answer = jobs[0][0]+jobs[0][1];
        int beforeSum = jobs[0][0]+jobs[0][1];
        for(int i=1; i<jobs.length; i++){
            answer+= Math.abs(beforeSum-jobs[i][0])+jobs[i][1];
            beforeSum+=jobs[i][1];
        }
        return answer/jobs.length;
    }
}

결과는 10점, 주어진 케이스는 통과했으나 테스트는 대부분 통과하지 못했다.

정렬 기준이 잘못된 것 같다.

30분 정도 생각을 해 봤지만, 별다른 수가 생각이 나지 않아, 답을 보고 이해하기로 했다.

잘 된 접근

크게 두 파트로 접근할 수 있다.

하나는, 이전의 진입 시간보다 작은 진입 시간을 가지는 작업을 모두 할 일에 넣기.

나머지는, 해당 작업을 처리하면서, 걸리는 시간(대기+소요)과 소요시간을 분리하여 관리할 것.
(현재 내 코드에서의 for문 내의 로직과 동일)

예를 들어서, (1, 2) (1, 3) (2, 5) 가 있다고 가정해보자.

이 상황에서, 일단 0에 진입할 수 있는 작업이 있었으면 넣었겠지만, 없기 때문에 소요 시간이 가장 작은 작업을 넣어야 한다,

(1, 2) 이므로, 이전 진입 시간은 1이 된다.

그리고 다시, 첫 번째 파트를 검증한다. 1보다 작거나 같은 진입시간을 가지는 작업을 큐에 넣는다. (1, 2)와 (1, 3) 이 된다.

이제 큐에서 작업을 꺼내면서, 로직을 처리한다. 총 소요시간 (꺼낸 작업의 소요 시간 + 이전까지의 대기 시간 - 현재 작업의 진입 시간)을 구한다.

이전 작업의 대기시간에 현재 작업의 대기시간을 더하여 데이터를 갱신한다.

로직을 처리하며 데이터를 갱신한 경우 count+1을 한다.

다시 처음부터 로직을 처리하면서, 모든 작업이 완료될 때 까지 반복한다.

최종적으로는, 총 소요시간 / 배열의 길이 = 평균 소요 시간 를 리턴한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int answer = 0;
        int cnt=0, end=0, idx=0;
        while(cnt < jobs.length){ // 모든 작업을 완료
            while(idx < jobs.length && jobs[idx][0] <= end){ // 진입 시간이 이전 대기 시간을 벗어나지 않는 경우
                que.offer(jobs[idx++]); // 작업 추가
            }
            if(que.isEmpty()) end = jobs[idx][0]; // 이전 대기 시간 갱신, 첫 작업의 진입시간이 1이 아닌 경우
            else {
                int cur[] = que.poll(); // 현재 처리 작업
                answer+= end - cur[0] + cur[1];
                end += cur[1];
                cnt++; // 작업 횟수 추가
            }
        }

        return answer/jobs.length;
    }
}

알게 된 점

없음.