[디스크 컨트롤러] - 힙(heap) ★★★☆ / 복습 ○

[ 문제 ] : https://programmers.co.kr/learn/courses/30/lessons/42627

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

---

[ 문제 접근 ]

 

우선 순위큐를 사용하여 작업의 소요시간이 작은 순으로 하나씩 뽑아내면 되겠다고 생각이 듬.

 

큐에 값을 하나씩 빼면서 시간을 계산해주고, 시간안에 들어온 작업들을 다시 큐에 넣어주면서 정답을 계산한다.

 

 

 

---

[ 최종 코드 ]

 

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

using namespace std;

struct cmp {
	bool operator()(std::pair<int, int> a, std::pair<int, int> b) {
		return a.second > b.second;
	}
};
int solution(vector<vector<int>> jobs) {
	int answer = 0;
	int size = jobs.size();
	std::priority_queue<std::pair<int, int>, vector<std::pair<int, int>>, cmp> pq;

	int time = 0, delay = 0;
	int cnt = 0;
    
    std::sort(jobs.begin(),jobs.end());

	for (int i = 0; i < size;i++) { // 모든 작업이 실행될때까지

		
		while (cnt < size && jobs[cnt][0] <= time) { 
			pq.push({ jobs[cnt][0], jobs[cnt][1] }); 
			cnt++;
		}

		if (pq.empty()) { // pq에 들어가지 못했을때
			time = jobs[cnt][0];  // time을 옮겨 들어가게끔.
			i--;
			continue;
		}

		delay = time - pq.top().first;
		answer += (delay + pq.top().second);
		time += pq.top().second;
		pq.pop();

	}


	return answer / size;
}

 

---

[ Key Point ]

 

👉 한 작업이 끝나고 다음 작업 요청이 와 있지 않거나, 바로 오지 않는 case도 생각해줘야한다.

---

[ 다른 사람 풀이 ]

 

ref :: https://transferhwang.tistory.com/446

ref :: https://mungto.tistory.com/15