[코딩테스트] Java 디스크 컨트롤러

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

가장 최소의 처리량 평균 시간을 구하는 문제였습니다. 요청시간이 빠른 순대로 정렬을 하면 짧은 작업시간을 가지는 일들에 대해서는 너무 오래 기다리게 되고, 짧은 작업시간 순대로 정렬을 하면 요청이 먼저 온 작업을 처리를 하지 못하게 됩니다. 

따라서 현재 시간에 따라 처리 가능한 작업을 구하고 그 중에서 요청시간이 짧은 것을 먼저 처리합니다.

소스코드

import java.util.*;

class Solution {
    
    static class Job implements Comparable<Job> {
        int requestTime, workingTime;
        
        public Job(int requestTime, int workingTime) {
            this.requestTime = requestTime;
            this.workingTime = workingTime;
        }
        
        @Override
        public int compareTo(Job j) {
            if (this.requestTime == j.requestTime) {
                return this.workingTime - j.workingTime;
            }
            return this.requestTime - j.requestTime;
        }
    }
    
    public int solution(int[][] jobs) {
        PriorityQueue<Job> disk = new PriorityQueue<>();
        int len = jobs.length;
        
        for(int[] job: jobs) {
            disk.add(new Job(job[0], job[1]));
        }
        
        int time = 0; // 현재 시간
        int ans = 0; // 처리량 평균 구하기
        List<Job> execList = new ArrayList<>();
        
        while (!disk.isEmpty() || !execList.isEmpty()) {
            // 현재 시간에 요청된 작업을 모두 execList에 추가
            while (!disk.isEmpty() && time >= disk.peek().requestTime) {
                execList.add(disk.poll());
            }

            // 작업을 소요 시간 기준으로 정렬
            if (!execList.isEmpty()) {
                Collections.sort(execList, Comparator.comparingInt(job -> job.workingTime));
                Job exec = execList.remove(0);
                if (time < exec.requestTime) {
                    time = exec.requestTime;
                }
                time += exec.workingTime;
                ans += time - exec.requestTime;
            } else if (!disk.isEmpty()) {
                time = disk.peek().requestTime;
            }
        }
        
        return ans / len;
    }
}

코드 설명

Job 클래스

• Job 클래스는 Comparable 인터페이스를 구현하며, 작업의 요청 시간(requestTime)과 소요 시간(workingTime)을 필드로 가지고 compareTo 메서드는 Job 객체를 요청 시간 순서로 정렬합니다. 요청 시간이 동일할 경우, 소요 시간 기준으로 정렬하도록 조건을 설정할 수 있습니다.

 

• PriorityQueue<Job> disk = new PriorityQueue<>();
  작업 요청 시간 기준으로 정렬되는 우선순위 큐를 초기화합니다. Job 객체를 담아 요청 시간이 빠른 순서대로 작업을 처리할 수 있습니다.
• while문 내부 변수 사용부분
  • time은 현재 시각을 나타내며, ans는 작업 완료까지 걸린 총 시간을 누적합니다.
  • execList는 현재 처리 가능한 작업 목록입니다.
• while (!disk.isEmpty() || !execList.isEmpty()) { ... }
  • disk 큐의 작업 중 현재 time에 요청된 작업을 execList로 이동합니다.
  • execList에 작업이 있으면 소요 시간 기준으로 정렬하고, 가장 짧은 작업을 선택하여 실행합니다.
  • time이 해당 작업의 요청 시간보다 작으면, time을 그 요청 시간으로 맞춥니다.
  • time을 해당 작업의 소요 시간만큼 증가시키고, 요청부터 종료까지 걸린 시간(time - requestTime)을 ans에 더합니다.
  • 만약 execList가 비어 있고 disk에 작업이 남아 있다면, time을 다음 작업의 요청 시간으로 설정하여 작업을 진행할 수 있게 합니다.