프로그래머스 - 디스크 컨트롤러 (lv3)

문제 설명

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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627

문제 풀이

※ 참고 : 2차원 Minheap class
https://github.com/juwith/jsutilspp/blob/master/sort-heap-2d/src/heapsort2d.cpp

소스코드 (CPP)

#include <string>
#include <vector>

#include <iostream>

using namespace std;

template <typename T>
class MinHeap
{
	vector<pair<int, T>> array;

public:
	MinHeap() {}
	void insert(int x, T item)
	{
		array.push_back(pair<int, T>(x, item));
		int target = array.size();
		while( target > 1 && x < array[(target/2)-1].first) {
			array[target-1].first = array[(target/2)-1].first;
			array[target-1].second = array[(target/2)-1].second;
			//cout << "target = " << target << ", target/2 = " << target/2 << endl;
			target /= 2;
			//cout << "target:" << target << endl;
		}
		//cout << "======end target========target:" << target << endl;
		array[target-1].first = x;
		array[target-1].second = item;
	}

	pair<int, T> popMin()
	{
		//min is always first factor by heapify(insert)
		pair<int, T> minpair(array.front().first,array.front().second);

		//end factor moves to first factor
		array.front().first = array.back().first;
		array.front().second = array.back().second;
		array.pop_back();

		//heapify
		int x = array.front().first;
		T xitem = array.front().second;
		int parent=1, child=2;
		int arrSize = array.size();
		while(child <= arrSize) {
			if(array[child-1].first > array[child].first) {
				child++;
			}
			if(x <= array[child-1].first) {
				break;
			}
			array[parent-1].first = array[child-1].first;
			array[parent-1].second = array[child-1].second;
			parent=child;
			child *= 2;
		}
		array[parent-1].first = x;
		array[parent-1].second = xitem;

		return minpair;
	}

	pair<int, T> getMin()
	{
		//min is always first factor by heapify(insert)
		return array.front();
	}


	bool isEmpty()
	{
		if(array.empty())
			return true;
		return false;
	}

	int factorSize()
	{
		return array.size();
	}

	void print()
	{
		cout << endl << "=============print=============" << endl;
		typename vector<pair<int, T> >::iterator iter;
		for(iter = array.begin(); iter != array.end(); iter++){
			cout<<iter->first << "(" << iter->second << ")" << " ";
		}
		cout << endl << "===============================" << endl;
	}

	void printtree(int index, int space)
	{
		if(array.size() < index) {
			return;
		}

		space += 4;
		printtree((index*2)+1, space); //right
		for(int i=4;i<space;i++) {
			cout << " ";
		}

		cout << array[index-1].first << endl;
		printtree((index*2), space); //left
	}
};


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

	int processingTime = 0;
	int currTime = 0;
	int starttime;
	int worktime;

	// jobs[start time][work time]
	// heapify by work time
	MinHeap<int> minheap;
	MinHeap<int> tempheap;
	

	for(int i=0;i<jobs.size(); i++) {
		minheap.insert(jobs[i][1],jobs[i][0]);
	}

	bool foundfactor;
	while(!minheap.isEmpty()) {
		foundfactor = false;
		while(!minheap.isEmpty()) {
			pair<int, int> min = minheap.popMin();
			starttime = min.second;
			worktime = min.first;
			//cout << "pop min start time : " << starttime << " work " << worktime << endl;
			if(currTime >= starttime) {
				int doneTime = currTime - starttime + worktime;
				currTime += worktime;
				processingTime += doneTime;
				//cout << "found min work time " << worktime << "(" << starttime << ") curr " << currTime <<" done time " << doneTime << " processingTime " << processingTime << endl;
				foundfactor = true;
				break;
			} else {
				//reverse insert
				tempheap.insert(starttime,worktime);
			}
		}

		if(!foundfactor) {
			/////////////min should be starttime in this case
			pair<int, int> min = tempheap.popMin();
			starttime = min.first;
			worktime = min.second;
			currTime = starttime + worktime;
			//cout << "curr " << currTime << endl;
			processingTime += worktime;
			//cout << "nothing to process on time, use work " << worktime << "(" <<starttime << ")" << " processingTime " << processingTime << endl;
		}

		while(!tempheap.isEmpty()) {
			pair<int, int> min = tempheap.popMin();
			minheap.insert(min.second,min.first);
		}

	}

	answer = processingTime/jobs.size();
	return answer;
}

해설

크게 2가지 작업이 필요하다고 생각했습니다.

1. 현재 시간보다 요청 시간이 짧은 순으로 처리함.

2. 현재 시간보다 요청 시간이 짧은 값이 없다면 요청시간이 가장 빠른 순으로 처리함. (idle)

1. 최소 작업시간 처리

가장 작은 작업시간을 찾기위해 heap에 작업시간이 작은 순으로 정렬합니다.

이 때 요청 시간은 현재 시간보다 이전 시간이어야 처리가 가능합니다.

2. idle 시 최소 시간 처리

현재시간이 요청시간보다 작다면, idle 시간이 존재한다는 의미 입니다.

idle 시간 이후에는 1번과 같이 요청시간이 작은 순서대로 처리를 해야합니다.

따라서 idle 시간 이후의 작업은 요청시간이 작은 순으로 정렬합니다.

이렇게 되면 해당 작업을 완료할 때 현재 시간은 작업시간과 요청시간을 더한값이 됩니다.

결과