99클럽 코테 스터디 5일차 TIL - 우선순위큐

항해99 코테 스터디 5일차 문제인 프로그래머스의 '디스크 컨트롤러'는 한번에 하나의 작업만 수행할 수 있는 하드디스크에 요청들이 들어왔을 때 모든 요청의 대기시간의 평균의 최솟값을 구하는 문제다. 난이도는 레벨3이며 우선순위큐를 통해 해결할 수 있다.

 

오늘의 문제 - 디스크 컨트롤러 문제 정보

문제 키워드

- 힙/우선순위큐

난이도

- Level 3

 

문제 요약

• 하드디스크는 한번에 하나의 작업만 해결할 수 있다.
• 작업 요청이 들어온 시간과 해당 작업을 수행하는데 걸리는 시간이 배열로 주어질 때, 모든 요청이 끝나고 각 요청의 평균 대기시간의 최소값을 구하라.

 

문제 풀이 과정  

• 디스크 스케줄링 기법은 선입 우선, 최소시간 우선 등이 있다. 이 문제에서는 각 작업이 끝날 때까지 기다린 대기시간이 최소화되어야 하므로, 최소시간 우선 기법을 사용할 것이다.
  • 따라서 우선순위큐를 이용해 삽입된 작업을 작업시간 오름차순으로 정렬되도록 하였다.
• 매 시간마다 현재 진행 중인 작업이 있는지 확인하고, 작업이 있다면 작업이 끝났는지 확인 후 종료시킨다.
• 현재 진행 중인 작업이 없다면 요청된 작업 중 가장 적게 걸리는 작업을 시작한다.
• 최종적으로 각 작업의 대기시간의 총합을 작업의 개수로 나누어 평균 시간을 반환하였다.
• 메인함수 구현의 편의성을 위해 Task라는 클래스를 만들고 편의성 함수들을 구현해놓았다.
  • 현재 시간에 작업이 끝났는지 확인하는 함수, 작업 대기시간을 구하는 함수 등

코드

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int N = jobs.length;
        
        // 작업 목록을 요청 시간별로 map으로 묶음
        Map<Integer, List<Integer>> jobTimeMap = new HashMap<>();
        for(int[] job: jobs) {
            int enterT = job[0], jobT = job[1];
            jobTimeMap.putIfAbsent(enterT, new ArrayList<>());
            jobTimeMap.get(enterT).add(jobT);
        }

        // 시간의 흐름에 따라 작업 요청, 작업 시작 및 종료 확인
        int t = 0, timeSum = 0, restJob = N;
        Task nowTask = null;
        PriorityQueue<Task> tasks = new PriorityQueue<>();
        while (restJob > 0) {
            // 현재 시간에 요청된 작업을 pq에 삽입
            if (jobTimeMap.containsKey(t)) {
                for(int jobT : jobTimeMap.get(t)) {
                    tasks.add(new Task(t, jobT));
                }
            }
            
            // 현재 작업이 끝났는지 확인
            if (nowTask != null && nowTask.isJobDone(t)){
                timeSum += nowTask.getWaitTime();
                restJob--;
                nowTask = null;
            }
            
            // 현재 진행중인 작업이 없으면 가능한 작업 중 
            // 작업 시간이 가장 짧은걸로 시작
            if (nowTask == null && !tasks.isEmpty()) {
                nowTask = tasks.poll();
                nowTask.setStartT(t);
            }
            
            t++;
        }
        
        return (int) timeSum / N;
    }
    
    class Task implements Comparable<Task> {
        int enterTime;
        int jobTime;
        int startTime;
        
        public Task (int enterTime, int jobTime) {
            this.enterTime = enterTime;
            this.jobTime = jobTime;
        }
        
        public void setStartT(int t) {
            this.startTime = t;
        }
        
        public boolean isJobDone(int nowT) {
            return nowT - startTime >= jobTime;
        }
        
        public int getWaitTime() {
            return startTime + jobTime - enterTime;
        }
        
        @Override
        public int compareTo(Task other) {
            if (this.jobTime == other.jobTime) {
                return this.enterTime - other.enterTime;
            }
            return this.jobTime - other.jobTime;
        }
    }
}

• 시간복잡도: O(N*T) → T: 최대 작업시간
• 공간복잡도: O(N)

 

오늘의 학습 회고

새롭게 알게된 것

• 오래전에 C++로 코딩테스트를 준비하던 시절에 풀었던 문제인데, 자바로 다시 푸니 새로웠다.
  • 새삼, c++보다 자바가 훨씬 편하고 가독성도 좋다는 생각이 들었다. 자바짱ㅎㅎ
• 이렇게 시간 기준으로 푼 문제는 시간복잡도를 계산하기가 어렵다ㅠㅠ