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

(6/28 - △) 히든 테스트 케이스들을 질문하기에서 알아내고 맞췄기 때문에

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

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

 

구현

현재 시점(time)에 따라 총 소요 시간이 적은 작업을 먼저 시작하면 평균값이 최소로 나온다.

1. 작업들을 {key:요청 시점, value: 총 소요 시간} 해싱을 이용하여 map에 저장한다. -> 요청 시점 key는 중복될 수 있으므로 multimap을 이용한다.

2. 현재 실행하고 있는 작업이 있는가? NO-> 2.1, YES->3

2.1. 현재 시점(time)에 따라 실행 가능한 작업들이 있는가? NO-> 7 YES-> 2.1.1

2.1.1. 작업들 중 소요 시간이 적은 작업을 시작한다.

3. 작업을 수행하고 있다는 느낌으로, 작업 시간(doing_time)을 카운팅한다.  (★쉴 시간 없이, 단계 2에서 작업을 넣어주므로 단계2  다음으로 바로 time++ 하지 않고 3으로 오도록 순서를 짜자.)

4. 수행하고 있는 작업의 작업 시간이 총 소요 시간보다 같거나 큰가? NO-> 6 YES->4.1

4.1. sum에 (현재 시간 - 요청 시점)을 더한다.

5. 모든작업을 끝냈는가? NO->2 YES->8

6. doing_time++

7. time++

8. sum에 작업 수를 나눈 후 answer에 넣는다.

 

예시1

 

 

예시2

 

코드

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0;

    int jobs_size = jobs.size();
    multimap<int, int> wait_m; // doing 되기 기다리는 작업들
    for (const auto& v : jobs) {
        wait_m.insert({ v[0], v[1] }); // 0 요청시점, 1 소요시간
    }
    
    int time = 0, doing_time = 0;
    pair<int, int> job_doing = {-1, -1}; // first 요청시점, second 총 소요시간
    int sum = 0; 
    int donejobs_cnt = 0;
    while (true) {
        // 진행 중인 작업이 없다면
        if (job_doing.first < 0) { 
            // 현재 do 할 수 있는 작업들 중에서, 소요 시간이 가장 작은 것 찾기
            pair<int, int> min = { 0, 1e9 }; // 요청시점, second 총 소요시간
            auto u_b = wait_m.upper_bound(time);
            auto l_b = wait_m.begin();
            if (u_b != l_b) { // 작업할 수 있는게 있으면
                for (; l_b != u_b; l_b++) {
                    if (l_b->second <= min.second) {
                        min = *l_b;
                    }
                }
                job_doing = min;
            }
        }
        // 진행 중인 작업이 있다면
        if (job_doing.first >= 0) {
            if (doing_time >= job_doing.second) { // 진행이 다 끝나면
                 // wait_m에서 해당 작업을 찾고 erase
                auto u_b = wait_m.upper_bound(job_doing.first);
                auto l_b = wait_m.lower_bound(job_doing.first);
                for (; l_b != u_b; l_b++) {
                    if (l_b->second == job_doing.second) {
                        wait_m.erase(l_b);
                        break;
                    }
                }
                sum += (time - job_doing.first);
                job_doing = { -1, -1 };
                doing_time = 0;
                donejobs_cnt++;
                if (donejobs_cnt >= jobs_size) {
                    break;
                }
                if (wait_m.empty()) {
                    break;
                }
                continue;
            }
            else { // 진행
                doing_time++;
            }
        }
        time++;
    }

    answer = (sum / donejobs_cnt);

    return answer;
}
int main()
{
    vector<vector<int>> v{ {0,9}, {0,4}, {0,5}, {0,7}, {0,3} };
    solution(v);
}