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

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

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

 

 디스크 작업이 진행되는 도중에 더 높은 우선순위를 가진 작업 명령이 입력되면

진행중이던 작업을 그만 두고 새로운 작업명령을 실행해야 하는가?라는 질문에 바로 답을 할 수 없어서 애먹었다.

 

문제의 조건에서 "하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다."를 보고 힌트를 얻었다. 작업을 진행하는 도중에는 우선순위가 높더라도 무시하겠지. 이렇게 문제를 읽고 숨겨진 의미를 파악하는게 코딩테스트의 묘미...일지도?

 

백터 안의 백터인 2차원 백터를 사용하지 않고 풀려고 노력했다.

bool compare(vector<int> v1, vector<int> v2){
    if(v1.at(0)==v2.at(0))
        return v1.at(1)<v2.at(1);
    else
        return v1.at(0) < v2.at(0);
}

int solution(vector<vector<int>> jobs) {
    // i는 정렬된 jobs의 작업을 어디까지 할당했는지 가르킨다. 
    // 아래에서 0을 넣었으므로 1부터 시작한다.
    sort(jobs.begin(), jobs.end(), compare);
    int i=1;

    priority_queue<int, vector<int>, greater<int>> pq;

    vector<int> save;
    // 넣지 않아도 상관없지만 넣으면 첫 번째 작업 완료 시간에서 시작할 수 있다.
    // 필요없다면     int i=0, seconds=0;를 대신 넣으면 된다.
    int seconds=jobs.at(0).at(0);
    pq.push(jobs[0][1]);

    // 작업이 완료될 때마다 save에 시간을 저장하므로 jobs와 save가 같아지면 종료시키면 된다.
    while( save.size()!=jobs.size() ){
        // Priority Queue가 차있는 경우.
        if(!pq.empty()){
            // 우선권을 가진 작업이 완료되는 시간대로 점프한다.
            seconds+=pq.top(); pq.pop();
            // 작업이 완료되는 시간을 저장한다.
            save.push_back(seconds);
            // 작업이 진행되는 도중 디스크에 들어온 명령을 넣지 못했으므로
            // 현재 시간까지 디스크에 넣어야할 작업을 채워준다.
            while(i<jobs.size() && jobs.at(i).at(0)<=seconds){
                pq.push(jobs[i][1]);
                i++;
            }
        // Priority Queue가 비어있는 경우.
        } else {
            // 시간이 지남에따라
            seconds++;
            // 작업명령을 넣어야할 시간이 되면 디스크에 채워준다.
            if(jobs.at(i).at(0)==seconds){
                pq.push(jobs[i][1]);
                i++; 
            }
        }
    }

    // (작업을 마친 시간 - 디스크에 삽입된 시간)의 총합 / 갯수가 정답이다.
    int sum=0;
    for(int i=0; i<jobs.size(); ++i){
        sum -= jobs[i][0];
        sum += save[i];
    }
    return sum / jobs.size();
}

 

시작 위치를 백터의 첫 번째 값으로 정해주지 않으면 속도 차가 많이 난다.

좌측 seconds가 0부터 시작

우측 seconds가 jobs의 첫 번째 값에서 시작

 

idx i를 사용할 때 꼭 i<s.size() 구문을 넣어야 Error가 나지 않는다. 또 이러한 에러를 쉽게 발견하기 위하여 .at()함수를 적극적으로 이용하는 것이 편하다.

 

priority_queue를 사용할 때도 pop를 하기 전에 empty()함수로 에러가 나오지 않도록 유의하자.