프로그래머스 - 디스크 컨트롤러(JAVA)

박상훈·2024년 2월 13일

알고리즘

목록 보기

3/6

문제 링크

풀이

하드디스크가 작업중이 아닐 때, 요청된 작업들 중 수행 시간이 짧은 작업 요청을 우선적으로 수행해야 return값이 최소가 된다. 이러한 부분은 그리디 알고리즘과 비슷한 면모를 보이는 것 같다.

그렇다면 어떻게 수행 시간이 짧은 것들을 먼저 요청할 수 있을까?

1. 새로운 요청이 들어올 때 마다 작업 요청 배열을 정렬하는 방법

해당 방법 사용 시 jobs의 길이는 1 이상 500 이하이기 때문에 시간복잡도 상으로 문제를 해결하는데 큰 문제는 없어보인다. 그렇지만 별로 효율적인 방법은 아닌 것 같다.

2. 하드디스크가 작업중이 아닐 때 작업 요청 배열을 스캔하여 수행 시간이 가장 짧은 작업 요청을 찾기

1번 방법과 마찬가지, 효율적인 방법은 아닌 것 같다.

3. 우선순위 큐를 사용하여 수행 시간이 짧은 작업 요청에 우선순위를 주기

이 방법이 가장 효율적인 방법인 것 같아 해당 방법으로 문제를 풀어보았다.

로직은 아래와 같다.

우선순위 큐 배열을 만든다. (각 index) == (jobs의 시작 시간)
jobs로 제공된 정보들을 우선순위 큐 배열에 PQ[jobs의 시작 시간] = { 해당 시작 시간의 작업 요청들 } 와 같은 형식으로 넣는다.
모든 jobs가 완료될 때 까지 1ms단위로 반복문을 돌린다.
3-1. 하드디스크가 작업을 수행하고 있지 않은 경우
i. 가장 먼저 들어온 작업 요청을 찾기 위해 작업 요청이 들어올 때 까지 반복문을 진행시킨다.
ii. 작업 요청이 들어오면 그 때 시작하는 모든 작업 요청들을 새로운 우선순위 큐(작업 시간이 짧은 것 기준)에 넣는다.
3-2. 하드디스크가 작업을 수행중인 경우
i. answer값에 수행중인 작업과 수행 대기중인 작업의 갯수의 합을 더한다.
ii. 수행이 완료되면 pq에서 해당 작업을 지운다.
iii. 수행하는 동안 들어왔던 작업 요청들을 pq에 삽입한다.
answer를 jobs의 길이(처음 들어왔던 작업 요청의 갯수)만큼 나눈 후 return한다.

코드

import java.util.*;

class Solution {

    class Pair{
        Integer start, length, end;

        Pair(Integer start, Integer length){
            this.start = start;
            this.length = length;
            this.end = start + length;
        }
    }

    PriorityQueue<Pair> pq = new PriorityQueue<>(((o1, o2) -> {
        if(o1.length == o2.length) return o1.start - o2.start;
        return o1.length - o2.length;
    }));

    public int solution(int[][] jobs) {

        int answer = 0;
        int next = 0;
        int complete = 0;
        PriorityQueue<Integer> v[] = new PriorityQueue[500001];
        ArrayList<Pair> nextJobs = new ArrayList<>();

        for(int[] i : jobs) {
            if(v[i[0]] == null) v[i[0]] = new PriorityQueue<>();
            v[i[0]].add(i[1]);
        }

        for (int i = 0; complete < jobs.length; i++) {

            // 작업을 수행하고 있지 않은 경우
            if (pq.isEmpty()){
                if(v[i] == null)
                    continue;
                while(!v[i].isEmpty())
                    pq.add(new Pair(i, v[i].poll()));

                next = pq.peek().end;

                continue;
            }

            // 작업을 수행중인 경우

            answer += pq.size() + nextJobs.size();

            if(v[i] != null){
                while(!v[i].isEmpty())
                    nextJobs.add(new Pair(i, v[i].poll()));
            }

            if(i == next) {
                pq.remove();

                pq.addAll(nextJobs);
                nextJobs.clear();

                complete++;
                if(pq.isEmpty()) continue;
                next += pq.peek().length;
            }


        }

        answer /= jobs.length;
        System.out.println(answer);
        return answer;
    }
}