[Algorithm] 프로그래머스 디스크 컨트롤러 (JAVA) 알고리즘 문제 풀이

안녕하세요! 오늘도 열심히 달리고 있는 젤리킹입니다. 최근 취업 코딩테스트로 알고리즘 문제들을 공부하고 있는데요. dfs, bfs는 어느정도 익숙해졌지만 그 외에 어려운 알고리즘은 아직도 해매는 경우가 많더라고요. 오늘부터 프로그래머스 1문제씩 꾸준히 풀려고 각오를 다지고 있습니다. 이번 포스팅에서는 디스크 컨트롤러 문제에 대해서 풀어보겠습니다.

 

문제

문제는 대략 이렇습니다. dfs, bfs 문제가 아닌 힙 알고리즘으로 

문제 해결 아이디어

• 대기큐와 실행큐를 나눠 선언한다
• 대기큐는 requestTime의 오름차 순으로 정렬 기준을 잡고 실행큐는 workingTime의 오름차순 정렬 기준을 잡는다.
• 대기큐에 jobs를 모두 넣는다. 그리고 time을 증가시키며 현재 시간 이하의 요청 시간을 가지는 모든 작업들을 대기큐에서 실행큐로 옮긴다.
• 작업시간이 짧을 수록 평균 시간이 작아지기 때문에 실행큐에서 poll을 하여 작업 시간과 평균 시간을 구하기 위해 answer에 값을 더한다.
• 들어온 작업수 만큼 모두 완료시까지 위와 같은 과정을 반복한다.

 

 

자바 코드

 

package com.company;

import java.util.*;

public class Main {

    public static class Job implements Comparable<Job> {
        int requestTime;
        int workingTime;

        public Job(int requestTime, int workingTime) {
            this.requestTime = requestTime;
            this.workingTime = workingTime;
        }

        @Override
        public int compareTo(Job o) {
            return this.requestTime - o.requestTime;
        }
    }

    public static int solution(int[][] jobs) {
        int answer = 0;

        PriorityQueue<Job> waiting = new PriorityQueue<>();
        PriorityQueue<Job> pq = new PriorityQueue<>(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                return o1.workingTime - o2.workingTime;
            }
        });

        for (int[] job : jobs) {
            waiting.offer(new Job(job[0], job[1]));
        }

        int cnt = 0;
        int time = 0;

        while (cnt < jobs.length) {

            while (!waiting.isEmpty() && waiting.peek().requestTime <= time) {
                pq.offer(waiting.poll());
            }

            if (!pq.isEmpty()) {
                Job tmp = pq.poll();
                time += tmp.workingTime;
                answer += (time - tmp.requestTime);
                cnt++;
            }else{
                time++;
            }
        }


        return answer / jobs.length;

    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        int[][] jobs = {{0, 3}, {1, 9}, {2, 6}};

        System.out.println(T.solution(jobs));
        //T.solution(n,number);

    }


}