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

문제요약

디스크 컨트롤러에 들어오는 명령(명령 시간, 소요시간)들이 배열로 주어집니다.
전체 명령들에 대해 대기시간+소요시간의 평균 최솟값을 구하세요.

메인 아이디어

아래 이유로 사실heap이라고 힌트써있어서 알고있긴했지만 이미 명령이 들어온 것들 사이에서 priorityqueue로 최소소요시간인 순으로 뽑아주는 시뮬레이션 문제임을 알게됐다.

이유

소요시간이 a,b인 명령이 대기중이라고 할 때 (지금은 디스크가 비었을 때로 이제 ab중 하나를 처리하려던 참이다) 이 때부터 대기시간+소요시간의 이득을 따져보자

a를 먼저하는 경우) a+(a+b) = 2a+b 만큼의 시간이 더 걸린다.
b를 먼저하는 경우) b+(b+a) = 2b+a 만큼의 시간이 더 걸린다.
참고로 두 경우 다 a와 b가 디스크가 빌 때까지 기다린 시간은 고정돼 있다.

그래서 a를 먼저하는 것이 더 좋다.

주의할 점

jobs배열이 시간 순이 아니라 따로 sort를 해줘야한다.

삽질

문제에서 다음과 같이 말했다.

하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

이 말은 16초부터 하드가 놀고 있을 때 요청이 18초에 여러개 들어온다면 sort 전 주어진 순서에 의해 결정되는 것처럼 들린다. 근데 그렇게 해석하면 안되고 그 안에서도 짧은 걸 고를 수 있다는 뜻이다.

[[0, 9], [0, 4], [0, 5], [0, 7], [0, 3]]의 경우 13이 나와야하는데
진행 중 빌 때의 처리는 잘해줬었는데 처음에 우르르 몰려올 때도 맨 앞거를 선택하면 안되고 시간 적게 걸리도록 선택할 수 있다는 것을 놓쳤다.
그래서 jobs sort에서 같은 시간에 들어와도 소요시간이 작은 순서를 도입했더니 해결됐다. (코드 version1)

sort때 하지 않고 처음에 같은 시간에 들어온 것들을 한번에 큐에 넣어줘도 괜찮다.(코드 version2) 개인적으론 version2가 더 마음에 든다.

코드 version1

sort에서 같은 시간에 들어온 작업을 정렬하여 0초에

#include <string>
#include <vector>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
struct input{
    int s, d;//start during
    input(int ss, int dd){
        s = ss;d=dd;
    }  
};
struct comp{
    bool operator()(input a, input b){
        return a.d>b.d;
    }
};

bool align_job(vector<int> &a, vector<int> &b){
    if(a[0]==b[0]) return a[1]<b[1];
    return a[0]<b[0];
}

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int time = 0;
    priority_queue<input, vector<input>,comp> q;
    sort(jobs.begin(),jobs.end(),align_job);
    
    //일단 하나를 넣자
    int i = 0;
    time = jobs[i][0];
    q.push(input(jobs[i][0],jobs[i][1]));
    i++;
    while(!q.empty()){
        //하나씩 처리해가면서 지금까지 시간 중에 넣을 수 있는 것들 넣고
        //empty가 도달하는 상황 막기 위해 처리할게 없으면 타임워프
        input cur = q.top();
        q.pop();
        time +=cur.d;
        answer+=time-cur.s;
        cout<<time<<" "<<time-cur.s<<endl;
        for(;i<jobs.size()&&jobs[i][0]<time;i++){//넣기
            q.push(input(jobs[i][0],jobs[i][1]));
        }
        if(!q.empty()){
            for(;i<jobs.size()&&jobs[i][0]==time;i++){//넣기
                q.push(input(jobs[i][0],jobs[i][1]));
            }
        }
        if(q.empty()&&i<jobs.size()){
            //일단 하나 넣고봐야하지 않을까..
            time = jobs[i][0];//일단 미래로 워프
            q.push(input(jobs[i][0],jobs[i][1]));
            i++;
        }
    }
    answer/=jobs.size();
    return answer;
}

코드 version2

#include <string>
#include <vector>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
struct input{
    int s, d;//start during
    input(int ss, int dd){
        s = ss;d=dd;
    }  
};
struct comp{
    bool operator()(input a, input b){
        return a.d>b.d;
    }
};

bool align_job(vector<int> &a, vector<int> &b){
    //if(a[0]==b[0]) return a[1]<b[1];
    return a[0]<b[0];
}

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int time = 0;
    priority_queue<input, vector<input>,comp> q;
    sort(jobs.begin(),jobs.end(),align_job);
    
    //일단 하나를 넣자
    int i = 0;
    time = jobs[i][0];
    q.push(input(jobs[i][0],jobs[i][1]));
    for(i++;i<jobs.size()&&jobs[i][0]==time;i++){//넣기
        q.push(input(jobs[i][0],jobs[i][1]));
    }
    while(!q.empty()){
        //하나씩 처리해가면서 지금까지 시간 중에 넣을 수 있는 것들 넣고
        //empty가 도달하는 상황 막기 위해 처리할게 없으면 타임워프
        input cur = q.top();
        q.pop();
        time +=cur.d;
        answer+=time-cur.s;
        cout<<time<<" "<<time-cur.s<<endl;
        for(;i<jobs.size()&&jobs[i][0]<=time;i++){//넣기
            q.push(input(jobs[i][0],jobs[i][1]));
        }

        if(q.empty()&&i<jobs.size()){
            //일단 하나 넣고봐야하지 않을까..
            time = jobs[i][0];//일단 미래로 워프
            q.push(input(jobs[i][0],jobs[i][1]));
            for(i++;i<jobs.size()&&jobs[i][0]==time;i++){//넣기
                q.push(input(jobs[i][0],jobs[i][1]));
            }
        }
    }
    answer/=jobs.size();
    return answer;
}