99클럽 코테 스터디 2일차 TIL : heap - 디스크 컨트롤러 (챌린저)

디스크 컨트롤러를 구현하는 문제였다.

runtime의 평균을 최소로 하는 문제이므로, 대기시간을 최대한 짧게 만들면된다.

다음 작업을 결정할 지금시점에서, 대기중인 task들 중 exetime이 가장 짧은 task를 우선적으로 처리하도록 구현한다.

---

1. 주어지는 jobs들을 "시간순서대로" 정렬한다 (heap이 아닌, 그냥 sort!)

2. jobs중, 현재시점에서 수행가능한 작업들을 고른다.

3. 수행가능한 작업들 중 exe time이 가장 짧은 작업을 수행한다. <- 수행가능한 작업들은 min_heap에 넣어줌

4. 2번부터 반복!

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


// Compare two Foo structs.
bool comparevec(const vector<int>& x, const vector<int>& y) 
{
    return x[1] > y[1];
}

bool comparetime(const vector<int>& x, const vector<int>& y) 
{
    return x[0] < y[0];
}

int solution(vector<vector<int>> jobs) {
    sort(jobs.begin(), jobs.end(), comparetime); // 시간순 정렬
    
    int answer = 0;

    int sum = 0;
    int time = 0; // 지금 시간
    int iter = jobs.size();
    int do_job = 0; // 수행한 작업
    int get_index = 0; // 대기작업 가져오기를 한 index
    vector<vector<int>> can_jobs; // 지금 시점에서 수행가능한 작업들 == 대기목록
    
    while(true){
        if(do_job == iter){
            break;
        }
        
        // 지금 시점에서 수행 가능한 작업들 가져오기
        for(get_index; get_index<iter; get_index++){
            if(jobs[get_index][0] > time){
                get_index -= 0;
                break;
            }else{
                can_jobs.push_back(jobs[get_index]);
            }
        }
        make_heap(can_jobs.begin(), can_jobs.end(), comparevec); // 수행시간 기준으로 정렬
        
        
        if(can_jobs.size() < 1){
            // 지금시점에서 수행 가능한 작업들 가져오기를 했는데 비어있음 == 지금 할일이 없음
            time += 1;
            continue;
        }
        // 지금시점에서 수행 가능한 작업들이 있음!
    
        vector<int> now_job = can_jobs[0];
        pop_heap(can_jobs.begin(), can_jobs.end(), comparevec);
        can_jobs.pop_back();
        time += now_job[1];
        int exetime = time - now_job[0];
        sum += exetime;
        
        
        do_job += 1;
        
    }
    
    answer = sum / iter;
    
    
    return answer;
}

---

1. jobs들이 당연히 시간순으로 정렬되어 있다고 생각하지 말기

난 jobs가 정렬되어서 들어온다고 생각했는데,,, 아니었다.

맨 처음에 sort를 이용해 시간을 기준으로 정렬한다.

 

2. compare 함수 정의

2차원 벡터의 경우, 그냥 sort나 make_heap을 사용했을 때 어떻게 정렬되는지 확신할 수 없었다.

in time 기준, exe time기준으로 정렬하는 compart함수를 만든다.

두개 다 오름차순으로 정렬하는데 sort일때랑 make_heap일때랑 비교방향이 다르다.

뭔가 구현이 다른가보다,, 이런부분은 어떻게 확인해야 하고 하나하나 외우고 있어야 하는걸까,,ㅋㅎ,,,,

 

3. break 타이밍 정하기

처음에는 jobs가 비어있을때로 생각했다. 하지만 구현에서 jobs 벡터는 변경되지 않는다!

can_jobs를 이용하는방법 -> 현재 시점에서 수행가능한 작업이 없지만, 앞으로 들어올 작업이 있을 수 있다!

이럴때는 그냥 time을 1증가시키고 다음 반복으로 넘어가야지, break를 하지 않는다

이를위해 do_jobs를 이용해 전체 jobs개수와 비교해서 break 타이밍을 결정했다.

 

---

구현이 전체적으로 너무 지저분한것같긴한데,, 일단 테스트는 통과했으니까...^^.............

깔끔한 코드를 짤수있는 방법을 어떻게 찾아야할까,, 그냥 많이 접해보는수밖에 없겠지..

챌린저문제는 꽤나 까다로운게 많은것같다,,

구글링없이 해결할 수 있을때까지 열심히해야지