힙(Heap) > 디스크 컨트롤러 (Level3)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.

1. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.
2. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
3. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
4. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.

예를들어

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 다음과 같습니다.

이 요청을 우선순위 디스크 컨트롤러가 처리하는 과정은 다음 표와 같습니다.

모든 요청 작업을 마쳤을 때 각 작업에 대한 반환 시간(turnaround time)은 작업 요청부터 종료까지 걸린 시간으로 정의합니다. 위의 우선순위 디스크 컨트롤러가 처리한 각 작업의 반환 시간은 다음 그림, 표와 같습니다.

우선순위 디스크 컨트롤러에서 모든 요청 작업의 반환 시간의 평균은 8ms(= (3ms + 16ms + 5ms) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해 주세요.

 

제한 사항

• 1 ≤ jobs의 길이 ≤ 500
• jobs[i]는 i번 작업에 대한 정보이고 [s, l] 형태입니다.
  • s는 작업이 요청되는 시점이며 0 ≤ s ≤ 1,000입니다.
  • l은 작업의 소요시간이며 1 ≤ l ≤ 1,000입니다.

 

입출력 예

 

입출력 예 설명

입출력 예 #1

• 문제에 주어진 예와 같습니다.

 

소스코드

struct Compare
{
	bool operator()(pair<int, int> a, pair<int, int> b)
	{
		return a.second > b.second;
	}
};

int solution(vector<vector<int>> jobs)
{
	int answer = 0;
	int time = 0;
	int count = 0; //실행 대기중인 작업의 수

	//Pair<요청시간, 작업시간> 작업시간 기준 오름차순(top하면 젤 작은것 나옴)
	priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> datas;
	
	//작업 요청시간 기준 오름차순
	sort(jobs.begin(), jobs.end());

	while (count < jobs.size() || datas.empty() == false)
	{
		//요청시간 기준으로 우선순위 큐에 적재
		if (count < jobs.size() && time >= jobs[count][0])
		{
			datas.push({ jobs[count][0], jobs[count][1] });
			count++;

			continue;
		}

		if (datas.empty() == false)
		{
			time += datas.top().second; //작업시간 계산
			answer += time - datas.top().first; //작업완료시간 - 대기한 시간 계산 = 요청시간 ~ 완료시간

			datas.pop();
		}
		else
		{
			//최초 작업이 0초가 아닐때
			time = jobs[count][0];
		}
	}
	answer /= jobs.size();

	return answer;
}

 

생각해 볼 것

우선순위 큐같은 경우 커스텀한 정렬방식을 사용할 때 구조체를 사용하는것 같다.

Operator( )기억해두자