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

디스크 컨트롤러

💫 첫 번째 풀이

---

• 코드 의도 : 분류는 힙인데.. 뭔지 모르겠다.,
• 결과 : 정확성 100점 (20/20), 총 100점

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

using namespace std;

bool compare(vector<int> v1, vector<int> v2)
{
	if (v1[1] == v2[1])
		return v1[0] < v2[0];

	return v1[1] < v2[1];
}

int solution(vector<vector<int>> jobs)
{
	sort(jobs.begin(), jobs.end(), compare);

	bool* completed = new bool[jobs.size()];
	for (int i = 0; i < jobs.size(); i++)
		completed[i] = false;

	int lastCompletedTime = 0;
	int sumOfElapsedTime = 0;

	for (int i = 0; i < jobs.size(); i++)
	{
		int curProcessIndex = -1;
		int earliestReqTime = 1001;
		int earliestReqIndex = -1;

		// 다음 작업을 찾는다.
		// 만약 당장 시작할 수 있는 작업이 없는 경우, 남은 작업 중 가장 먼저 요청된 작업을 찾는다.
		for (int ji = 0; ji < jobs.size(); ji++)
		{
			if (completed[ji])
				continue;

			if (jobs[ji][0] < earliestReqTime)
			{
				earliestReqTime = jobs[ji][0];
				earliestReqIndex = ji;
			}

			if (jobs[ji][0] > lastCompletedTime)
				continue;

			completed[ji] = true;

			curProcessIndex = ji;
			break;
		}

		if (curProcessIndex != -1)
		{
			sumOfElapsedTime += jobs[curProcessIndex][1] + (lastCompletedTime - jobs[curProcessIndex][0]);
			lastCompletedTime += jobs[curProcessIndex][1];
		}
		else
		{
			int breakTime = earliestReqTime - lastCompletedTime;
			completed[earliestReqIndex] = true;

			sumOfElapsedTime += jobs[earliestReqIndex][1] + earliestReqTime - jobs[earliestReqIndex][0];
			lastCompletedTime += jobs[earliestReqIndex][1] + breakTime;
		}
	}

	delete[] completed;
	return sumOfElapsedTime / jobs.size();
}

---

자료구조에서 힙을 배우긴 했었지만..
어떻게 쓸지를 몰라 그냥 무작정 풀었다.

역시 나 스스로가 많이 부족하다고 느꼈다.

💫 최종 풀이

---

• 코드 의도 : 좋아보이는 풀이를 보고 배끼자, (Priority Queue, Template, Iterator)
• 결과 : 정확성 100점 (20/20), 총 100점

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

using namespace std;

struct CompareProcessTime
{
	bool operator()(const vector<int>& v1, const vector<int>& v2)
	{
		// 우선순위 큐는 큰 것 순서대로 정렬하기 때문에,
		// 오름차순으로 만들어주기 위해서는 정렬 순서를 반대로
		return v1[1] > v2[1];
	}
};

struct CompareReqTime
{
	bool operator()(const vector<int>& v1, const vector<int>& v2)
	{
		return v1[0] < v2[0];
	}
};

int solution(vector<vector<int>> jobs)
{
	priority_queue<vector<int>, vector<vector<int>>, CompareProcessTime> pq;

	sort(jobs.begin(), jobs.end(), CompareReqTime());
	auto it = jobs.begin();

	int sumOfElapsedTime = 0;
	int curTime = jobs[0][0];

	while ((it != jobs.end()) || !pq.empty())
	{
		while ((it != jobs.end()) && ((*it)[0] <= curTime))
		{
			pq.push((*it));
			it++;
		}

		if (!pq.empty())
		{
			curTime += pq.top()[1];
			sumOfElapsedTime += (curTime - pq.top()[0]);
			pq.pop();
		}
		else
		{
			curTime = (*it)[0];
		}
	}

	return sumOfElapsedTime / jobs.size();
}

다른 분들의 풀이를 보다가, 제일 깔끔해보이는 코드가 이거였다.
CPP의 Priority Queue, Template, Iterator를 이번에 배웠다.

Priority Queue는 기본적으로 내림차순으로 정렬을 하기에,
오름차순으로 정렬되는 Compare 구조체를 만들 때 리턴을 반대로 줘야했다.
우선순위가 더 높은 것에 true를 리턴해줘야 했다.

Compare 구조체도 사실 이번에 알았다.
기존에는 첫 번째 풀이처럼 Compare 함수를 만들어 넣었었는데,
괄호 연산자를 재정의하는 구조체는 이번에 처음 써보았다.

Template은 모두의 코드에서 공부했다.
궁금한 것들이 죄다 있어서 유익했다.

Iterator는 C#랑 비슷한 것 같은데,
사실 C#에서도 별로 써본적이 없어서.. ㅎㅎ..
더 공부해봐야 할 것 같다.

Container Adapter? 라는 것도 잘 와닿지않는다.
마찬가지로 더 공부해야겠다..