디스크 컨트롤러

programmers.co.kr/learn/courses/30/lessons/42627

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

<JAVA>

import java.util.*;
class Solution {
    public int solution(int[][] jobs) {
            
        Arrays.sort(jobs,(o1,o2)->o1[0]-o2[0]); // 오름차순 정렬
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]); //람다식을 이용해서 배열의 첫번째 자리수 기준으로 정렬하는 최소힙 정의
        
        int idx =0; // 작업의 인덱스
        int cnt =0; 
        int end=0; //마지막으로 작업이 끝난시간
        int answer =0;
        while(cnt<jobs.length){ //작업이 아직 다 수행이 되지 않았을때
            
            while(idx<jobs.length && end>= jobs[idx][0]){ //대기상태에 있거나 바로시작가능할경우 
                pq.add(jobs[idx]); // 우선순위 큐에 넣어준다
                idx++; // 다음 작업
            }
            
            if(pq.isEmpty()){ // 현재 end 시간에 수행해야할 작업이 없다면
            
                end = jobs[idx][0]; // 그다음 작업의 들어오는 시점을 end로 바꿔준다
            }
            else{
                
                int[]a = pq.poll(); 
                answer = answer + end-a[0]+a[1]; // 대기부터 마지막까지 
                end = end+a[1]; //작업마지막으로끝낸시간 변경
                cnt++; // 완료된 작업수 증가 시키기 
               
            }
            
            
            
        }
        
        return answer/jobs.length; //평균

    }
}

문제를 푸는 방법 

1. 작업수행 시간이 짧은게 먼저 수행 해야 평균이 낮게 나온다. 

2. 앞에 작업이 끝남과 동시에 그다음 수행할 수 있는 대기상태에 있는 작업들중 가장 수행시간이 짧은 것을 먼저 수행해야한다. 작업시간은 짧은데 대기상태에 있지않거나 바로 시작할 수 없다면 해당 작업은 수행할 수 없다. 

3. 현재 상태에서 작업을 수행할 수 있는 것들은 모두 priority 큐에 넣어준다. 그리고 그 큐안에서 가장 작업시간이 짧은게 바로 나올 수 있도록 최소힙으로 정의해야한다. 

 

<C++>

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include<queue>
#include <iostream>
using namespace std;


struct cmp {
    bool operator()(vector<int>a, vector<int>b){
        return a[1]>b[1];
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int t=0;
    int time =0;
    sort(jobs.begin(), jobs.end());
    priority_queue<vector<int>,vector<vector<int>>,cmp>pq;
    while(t<jobs.size() || !pq.empty()){
        if(jobs.size()>t && time>=jobs[t][0]){
            pq.push(jobs[t]);
            t++;
            continue;
        }
        if(!pq.empty()){
            time +=pq.top()[1]; //가장 작은 시간
            answer += time-pq.top()[0];
            pq.pop();
        }
        else{
            time = jobs[t][0];
        }
    }
    answer = answer/jobs.size();
    return answer;
}

헷갈렸던 점 

 

- 최소 힙을 priority_queue<vector<int>, vector<vector<int>>,cmp>pq 로 구현하는 것을 알게됨

- time 을 기준으로 그 이하인 시간에 시작하는 요청들만 우선순위 큐에 넣어준다. 그리고 우선순위 큐에서 최소값의 요청을 구한 후 비게되면 time을 그다음 jobs 의 원소의 시작시간으로 정해준다.