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

programmers.co.kr/learn/courses/30/lessons/42627?language=cpp

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

 

문제 풀이

1. 처음에는 순열을 이용하여 모든 경우의수로 접근했으나 풀리지 않았다. (문제를 꼼꼼히 읽어봐야한다..)

 

2. jobs[X][0]은 요청온 시간이며, jobs[X][1]은 작업이 소요되는 시간이다.

 

3. jobs를 요청 온 시간으로 오름차순으로 정렬한다.

 

4. 작업량이 적은 순으로 priority_queue를 생성했다.

 

5. 현재 시간에 들어온 작업 중 가장 작업량이 적은 순으로 계산을 진행하면 정답을 구 할 수 있다.

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct cmp {
	bool operator()(vector<int> a, vector<int> b) {
		return a.at(1) > b.at(1);
	}
};

int solution(vector<vector<int>> jobs) {
	int answer = 0;
	int jobsTotal = jobs.size();
	int curTime = 0;
	int count = 0;
	int idx = 0;
	
	//0index(시간) 오름차순 정렬
	sort(jobs.begin(), jobs.end());

	//1index내림차순 정렬(작업량)
	priority_queue<vector<int>, vector<vector<int>>, cmp> pq;

	while (count < jobsTotal) {
		while (jobsTotal > idx && curTime >= jobs[idx][0]) {
			pq.push(jobs[idx++]);
		}

		if (pq.empty()) {
			//다음 작업으로 이동
			curTime = jobs[idx][0];
		}
		else {
			vector<int> cur = pq.top(); pq.pop();
			curTime += cur[1];
			answer += curTime - cur[0];
			count++;
		}
	}
	return answer/jobsTotal;
}