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

우선 문제에서 요구하는 CS지식이 있어서 문제를 이해하는데 한참 걸렸다.

어떤 알고리즘을 사용해야하는가?

일단 문제를 보다보면 job이 이렇게 주어지니 job = [작업이 요청되는 시점, 작업의 소요시간]이라고할때 job을 요청되는 시점 기준으로 정렬해야한다는건 직관적으로 이해가 가능하다.

그렇다면 그 다음부터는 어떻게 작업해야할까?
우선 시뮬레이션처럼 코드로 요청사항을 구현한다고 치자

1. 맨처음 작업해야하는건 [0,3]일거다.
2. 그러면 0번째의 작업이 3초동안 작업하는동안 그 다음 요청들을 대기열에 걸어둔다. (3초동안 1번째 요청과 2번째 요청이 들어와있을것이다.)
3. 0번째의 작업이 끝나고나면 그 다음 요청을 작업한다.

여기서 헷갈리는건 3번이다. 다음 요청인 [1,9]가 아닌 [2,6]을 작업해야한다. 이때 소요시간이 짧은걸 골라야한다.

그렇다면 단순히 소요시간이 짧은걸 고르는건가? 이때가 중요하다! 0번째작업이 작업하는동안!!!! 대기열에 걸린것들 중에서! 소요시간이 짧은것! 을 골라야한다. 즉 이 대기열에 올려주는 행위가 중요한거다.

1. 맨처음 작업해야하는건 [0,3]일거다.
2. 그러면 0번째의 작업이 3초동안 작업하는동안 그 다음 요청들을 대기열에 걸어둔다. (3초동안 1번째 요청과 2번째 요청이 들어와있을것이다.)
2-1. 대기열에 걸린 것 중 소요시간이 짧은순대로 정렬한다.
3. 0번째의 작업이 끝나고나면 그 다음 요청을 작업한다.

이렇게되는데 여기서 2-1를 heap으로 구현한다고 생각하면 된다.

동작 순서도

아래 코드는 그냥 챗GPT가 짠 최적의 코드다. 코드의 내용보단 이 코드가 어떻게 동작하는지 설명하겠다.

import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    public static int solution(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]); // 작업을 요청 시간에 따라 정렬
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 소요 시간이 짧은 순으로 처리하기 위한 힙
        int time = 0; // 현재 시간
        int totalTime = 0; // 총 소요 시간

        int i = 0; // jobs 배열을 탐색하기 위한 인덱스
        while (i < jobs.length || !minHeap.isEmpty()) {
            while (i < jobs.length && jobs[i][0] <= time) { // 현재 시간 이전에 들어온 작업을 힙에 추가
                minHeap.add(jobs[i]);
                i++;
            }

            if (!minHeap.isEmpty()) { // 작업을 처리할 수 있는 경우
                int[] job = minHeap.poll();
                time += job[1]; // 현재 시간 업데이트
                totalTime += time - job[0]; // 총 소요 시간 업데이트
            } else { // 대기 중인 작업이 없는 경우
                time = jobs[i][0]; // 대기 중인 작업이 없으므로 현재 시간을 다음 작업의 요청 시간으로 업데이트
            }
        }

        return totalTime / jobs.length; // 평균 소요 시간을 계산하여 반환
    }
}

 

1. 맨처음 0번째로 들어온 일은 3초가 걸린다. 3초의 시간이 지나는 동안 1초대에 요청이 들어온 1번째일과 2초대에 요청이 들어온 2번째일이 3초가 지나기전동안 대기열(minheap)에 걸리게된다.

2. 0번째의 일이 끝나고 대기열(minheap)에서 0번째의 일이 빠져나가면 이제 소요시간을 기준으로 그 다음 작업을 찾게된다.

3. 결국 이건 특정값을 기준으로 계속해서 정렬해주는 자료구조를 사용해야하는데, pop개념과 정렬 개념이 사용된 걸로보아 다들 예상했겠지만 이건 우선순위 큐(힙)로 그리디 알고리즘을 구현하는 문제다.

어떤 부분이 그리디한가?

그리디 알고리즘은 현재상황에서 최적의 선택을 하는 알고리즘이므로, 위 알고리즘에서 대기열에 걸린 것중 다음 작업을 선택하는 과정에서 짧은 소요시간을 기준으로 선택한다는 점에서 그리디라고 볼 수 있다.

---

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

프로그래머스