[프로그래머스 알고리즘 고득점 Kit][힙(Heap)][Java] 디스크 컨트롤러

 

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

작업을 요청 시각 기준으로 정렬한 뒤, 현재 시각까지 요청된 작업만 우선순위 큐에 넣는다.

우선순위 큐에서는 다음 순서로 작업을 선택한다.

소요 시간 → 요청 시각 → 작업 번호

 

전체 흐름은 다음과 같다.

작업을 요청 시각순으로 정렬
→ 대기 큐가 비었다면 다음 요청 시각까지 이동
→ 현재 시각까지 요청된 작업을 모두 대기 큐에 추가
→ 우선순위가 높은 작업 실행
→ 종료 시각 - 요청 시각을 반환 시간에 누적
→ 모든 작업의 평균 반환 시간 계산

 

waitingIndex를 사용해 아직 대기 큐에 넣지 않은 작업의 위치를 관리한다.

시간 복잡도

• 작업 정렬: O(N log N)
• 우선순위 큐 삽입·삭제: O(N log N)
• 전체 시간 복잡도: O(N log N)
• 공간 복잡도: O(N)

 

import java.util.*;

class Solution {
    
    class Job {
        int number;
        int requestTime;
        int duration;
        
        Job(int number, int requestTime, int duration) {
            this.number = number;
            this.requestTime = requestTime;
            this.duration = duration;
        }
    }
    
    public int solution(int[][] jobs) {
        List<Job> jobList = new ArrayList<>();
        int jobCount = jobs.length;
        for(int i=0; i<jobCount; i++) {
            jobList.add(new Job(i, jobs[i][0], jobs[i][1]));
        }
        Collections.sort(jobList, (j1, j2) -> {
            return Integer.compare(j1.requestTime, j2.requestTime);
        });
        
        PriorityQueue<Job> pq = new PriorityQueue<>((j1, j2) -> {
            if(j1.duration == j2.duration) {
                if(j1.requestTime == j2.requestTime) {
                    return Integer.compare(j1.number, j2.number);
                }
                return Integer.compare(j1.requestTime, j2.requestTime);
            }
            return Integer.compare(j1.duration, j2.duration);
        });
        
        int waitingIndex = 0;
        int currTime = 0;
        int totalReturnTime = 0;
        int completedJobCount = 0;
        
        
        while(completedJobCount < jobCount) {

            //대기큐에 들어있는 작업이 없다. -> 더 이상 요청한 작업이 없다. -> 현재시각이 다음 작업의 요청시간보다 앞선 상태 그래서 다음 작업의 요청 시각으로 현재 시각을 옮겨 줘야함.
            if(pq.isEmpty()) {
                currTime = Math.max(currTime, jobList.get(waitingIndex).requestTime);
            }
            //이전 작업의 끝 시각(현재시각)보다 이전에 시작하는 작업들을 대기큐에 넣어줌.(문제 설명 4번, 들어오는 오는 시점이 겹친다면 ... 대기 큐에 저장한 뒤... )
            for(int i=waitingIndex; i<jobCount; i++) {
                Job job = jobList.get(i);
                if(currTime >= job.requestTime) {
                    pq.add(job);
                    waitingIndex++;
                } else {
                    break;
                }
            }

            
            Job currJob = pq.poll();
            if(currTime < currJob.requestTime) {
                currTime = currJob.requestTime;
            }
            currTime += currJob.duration;
            totalReturnTime += currTime - currJob.requestTime;
            completedJobCount++;
        }
        
        return totalReturnTime / jobCount;
    }
}

처음엔 대충 이해하고 
우선순위큐에 다 때려넣고 시작해서 뭐가 틀린지 한참을 찾았다.
문제를 자세하게 읽자