(Python, Java) 프로그래머스 - 디스크 컨트롤러

24 Feb 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

import heapq


def solution(jobs):
    length = len(jobs)
    heapq.heapify(jobs)

    cur = 0
    sum = 0
    while jobs:
        temp = []
        # 현재 시간 혹은 이전에 들어온 것 추출해서 temp에 넣기
        while jobs and jobs[0][0] <= cur:
            temp.append(heapq.heappop(jobs))

        # temp에 값이 있다면 가장 먼저 끝나는 것 고르고 다시 큐에 넣어주기
        if temp:
            temp.sort(key=lambda x: x[1], reverse=True)
            in_time, cost = temp.pop()
            cur += cost
            sum += cur - in_time
            while temp:
                heapq.heappush(jobs, temp.pop())

        # temp가 비어있다는 것은 현재 시간에 수행할 작업이 없다 -> 현재 시간을 가장 빠른 inTime으로 업데이트
        else:
            task = heapq.heappop(jobs)
            cur = task[0]
            heapq.heappush(jobs, task)

    return sum // length

Java 풀이

import java.util.*;

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

        PriorityQueue<Job> q = new PriorityQueue();
        for (int[] job : jobs) {
            q.add(new Job(job[0], job[1]));
        }

        int cur = 0;
        int sum = 0;

        while (!q.isEmpty()) {
            LinkedList<Job> temp = new LinkedList<>();
            while (!q.isEmpty() && q.peek().inTime <= cur) {
                temp.add(q.poll());
            }

            if (temp.isEmpty()) {
                Job job = q.peek();
                cur = job.inTime;
            } else {
                temp.sort(new Comparator<Job>() {
                    @Override
                    public int compare(Job o1, Job o2) {
                        return Integer.compare(o1.cost, o2.cost);
                    }
                });
                Job curTask = temp.pollFirst();
                cur += curTask.cost;
                sum += cur - curTask.inTime;

                while (!temp.isEmpty()) {
                    q.add(temp.poll());
                }
            }
        }

        return sum / jobs.length;
    }

    private class Job implements Comparable<Job> {
        int inTime;
        int cost;

        public Job(int inTime, int cost) {
            this.inTime = inTime;
            this.cost = cost;
        }

        @Override
        public int compareTo(Job o) {
            return Integer.compare(inTime, o.inTime);
        }
    }
}