[프로그래머스 문제풀이] 13. 디스크 컨트롤러

작업 당 소요 시간을 계산 할 때 전체 소요 시간이 필요하기 때문에 전체 소요 시간과 작업 당 소요 시간을 둘 다 계산해줘야 한다.

어떤 작업을 요청하는 시간이 현재 작업 진행 시간모다 크면 그 작업을 이어붙일 수가 없기 때문에 다음과 같이 조건을 걸어 둔다.

if (jobs[i][0] <= total_time)

이 코드는 공회전이 많기 때문에 total_time++ 대신에
total_time = min_element(jobs.begin(), jobs.end())->at(0)를 써서 공회전을 줄여 보려 했지만
대체로 테스트케이스 소요 시간이 더 나쁘게 나왔다.
벡터의 사이즈가 크지 않다면 공회전을 감안하더라도 포인터 참조를 줄이는 것이 성능이 좋다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

#include <iostream>

using namespace std;

int solution(vector<vector<int>> jobs) {
    int total_time = 0;
    int work_time = 0;
    int size = jobs.size();

    sort(jobs.begin(), jobs.end(), [](vector<int> a, vector<int> b) {
        return a[1] < b[1];
        }); // 소요시간으로 우선 배열

    while (true) {
        for (int i = 0; i < jobs.size(); i++) {
            if (jobs[i][0] <= total_time) {
                total_time += jobs[i][1];
                work_time += total_time - jobs[i][0];
                if (jobs.size() == 1)
                    return work_time / size;
                jobs.erase(jobs.begin() + i);
                break;
            }

            if (i == jobs.size() - 1) total_time++;
        }
    }
}

int main()
{
	cout << solution({ { 0,3 }, { 1,9 }, { 2,6 } }) << endl;
	cout << solution({ {0, 5} ,{2, 10},{10000, 2} }) << endl;
}

디스크 컨트롤러 문제 링크