[Algorithm] 프로그래머스 디스크 컨트롤러

코딩테스트 연습 - 디스크 컨트롤러

 

풀이

1. 실행이 가능한 작업 중에서 소요 시간이 적은 작업부터 진행한다.

2. 실행이 가능하지 않은 작업은 작업 시작 시간 순으로 정렬하고 꺼내 실행 가능한 작업으로 보낸다.

 

위의 조건을 맞추기 위해, 작업 시작 시간과 작업 소요 시간을 멤버변수로 갖는 Work 객체를 생성한다.

그리고 각각의 조건으로 정렬되고, 앞에서부터 꺼내서 사용할 수 있는 우선순위 큐를 사용한다.

 

작업 목록에 모든 작업을 저장한다.

 

먼저 현재 시간 0초부터 시작한다.

작업 목록에서 현재 시간에 시작할 수 있는 (현재 시간보다 작업 시작 시간이 앞선) 작업 목록을 작업 대기 공간으로 이동한다.

 

작업 대기 공간이 비어있다면, 현재 진행할 수 있는 작업이 없으므로 현재시간을 +1초하고 넘어간다.

 

작업 대기 공간에 있는 작업에서는 소요 시간이 가장 적은 작업부터 진행한다.

작업이 진행되면 현재 시간은 작업 소요시간 만큼 증가하고,

전체 작업 소요 시간은 작업 소요 시간에 대기열에 들어와 현재 시간까지 대기한 시간만큼 증가한다.

 

전체 소스코드

import java.util.*;

class Work {
    private int request;
    private int time;
    
    public Work(int request, int time) {
        this.request = request;
        this.time = time;
    }
    
    public int getRequest() {return this.request;}
    public int getTime() {return this.time;}
}

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        // 요청 시간 순으로 정렬
        // 작업 목록
        PriorityQueue<Work> works = new PriorityQueue<>(
            (w1, w2) -> Integer.compare(w1.getRequest(), w2.getRequest())
        );
        for (int i = 0; i < jobs.length; i++) {
            works.offer(new Work(jobs[i][0], jobs[i][1]));
        }
        
        // 시작할 수 있는 작업 중 가장 짧은 작업 먼저 실행한다.
        // 시작할 수 있는 작업, 작업 소요시간 순으로 정렬
        // 작업 대기 공간
        PriorityQueue<Work> pq = new PriorityQueue<>(
            (w1, w2) -> Integer.compare(w1.getTime(), w2.getTime())
        );
        
        // 현재 시간
        int current = 0;
        // 수행한 작업 수
        int cnt = 0;
        while (cnt < jobs.length) {

            // 현재 시간에서 실행할 수 있는 작업을 우선순위 큐로 옮기고 작업 진행
            // 작업 목록에 작업이 남아있고, 시작할 수 있는 작업인 경우
            while (!works.isEmpty() && works.peek().getRequest() <= current) {
                pq.offer(works.poll());
            }
            
            // 작업 대기 공간에 작업이 있다면
            if (!pq.isEmpty()) {
                Work now = pq.poll();
                // 작업 소요 시간
                answer += now.getTime();
                // 대기한 시간
                answer += current - now.getRequest();
                
                // 현재 시간은 작업 소요시간만큼 증가한다.
                current += now.getTime();
                cnt++;
            } else {
                // 시작할 수 없는 경우 현재시간++ 후 기다림
                current++;
            }

            
        }
        // / 연산은 자동으로 내림
        return answer / jobs.length;
    }
}