[프로그래머스/알고리즘] 디스크 컨트롤러

디스크 컨트롤러

문제 설명

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

입출력 예

jobs : [[0,3],[1,9][2,6]] return : 9

해결과정

이 문제의 가장 중요한 것은 jobs의 배열 순서를 정렬하는게 중요하다 요청하는 것은 랜덤으로 들어오기 때문에 작업이 요청되는 시점을 기준으로 정렬을 해야 합니다

제가 작성한 알고리즘은 c++같은 경우는 STL의 sort함수(algorithm헤더)를 이용하고 정렬 기준은 Pred1라는 연산자 오버로딩을 만들어서 구현을 했습니다.

작업 시점을 work라고 하고 0부터 1개씩 늘리면서 수행했습니다. 해당 작업에 요청이 있으면 우선순위 큐를 이용해서 가져오는 방법을 사용 했고,  우선순위 큐는 정렬 기준을 Pred를 이용해서 작업의 소요시간이 가장 짧은 순으로 정렬 해줘야 요청부터 종료까지 걸린 시간의 평균이 줄어듭니다. 

need_work라 변수를 이용해서 우선순위 큐에서 가져온 작업 량을 넣어서 1개씩 수행을 하게 하고, 가져온 작업의 need_work만큼은 실행시간이므로 작업 시간(total)에 더해줘야 합니다.

우선순위 큐에 남아있는 것들은 각각에 요청 소요시간을 더해줘야 합니다. 그렇게 때문에 우선순위 큐의 사이즈만큼 total의 더해줘야 원하는 답이 나옵니다. 

만약 해결과정이 제대로 안나올 경우 작업이 0번째로 시작하지 않을 경우와 중간에 작업이 없는 경우와 작업이 n 시점에 여러개의 요청이 들어왔을 경우를 고려해서 작업해야 합니다

소스코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

struct Pred {
	bool operator()(vector<int> a, vector<int> b) {
		return a[1] > b[1];
	}
};

bool Pred1(vector<int> a, vector<int> b) {
	return a[0] < b[0];
}


int solution(vector<vector<int>> jobs) {
	priority_queue<int, vector<vector<int>>, Pred> temp;
	sort(jobs.begin(), jobs.end(), Pred1);
	vector<int> temp1;
	int answer = 0;
	int total = 0;			
	int work = 0;			//현재 수행한 작업
	int need_work = 0;		//해야할 작업
	int i = 0;
	while (1) {
		while (i!=jobs.size()) {
			if (jobs[i][0] == work)
			{
				temp.push(jobs[i]);
				i++;
			}
			else break;
		}

		if (need_work <= 0&&!temp.empty())
		{
			temp1 = temp.top();
			temp.pop();
			need_work = temp1[1];
			total += temp1[1];
		}
		
		total += temp.size();
		need_work--;
		work++;


		if (temp.empty() && need_work == 0 && i == jobs.size()) {
			break;
		}
	}
	answer = total / jobs.size();
	return answer;
}