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

---

📌 문제 설명

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

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

 

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

 

📌 제한 사항

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

📌 입출력 예

jobs	return
[[0, 3], [1, 9], [3, 5]]	8

 

🔗 문제 링크

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

프로그래머스

---

반응형

💡 풀이 아이디어

• 최소 힙(우선 순위 큐) 사용

📝 최종 풀이

• 요청 시간대로 처리하기 위해 jobs를 오름차순으로 정렬합니다.
• 소요 시간을 기준으로 저장하기 위한 대기 큐를 우선 순위 큐로 선언합니다.
• 현재 시간 이전에 요청된 작업들을 대기 큐에 추가합니다.
  • 이 때, 우선 순위가 높은 순서인 { 소요 시간, 요청 시각 } 형식으로 추가합니다.
• 대기 큐에 작업이 들어 있으면 우선 순위가 높은 작업을 처리합니다.
  • 현재 시간을 갱신하고 반환 시간을 더합니다.
• 대기 큐가 비어있으면 다음 작업의 요청 시간으로 이동합니다.
• 이 과정을 모든 작업이 완료될 때까지 반복합니다.
• 최종적으로 평균 반환 시간 ( 총 반환 시간 / 작업 수) 을 return 합니다.

---

728x90

👩‍💻 코드

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

using namespace std;

int solution(vector<vector<int>> jobs) {
    sort(jobs.begin(), jobs.end());
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    int time = 0;
    int answer = 0;
    int index = 0;
    int count = jobs.size();
    
    while (index < count || !pq.empty()) {
        while (index < count && jobs[index][0] <= time) {
            pq.push({jobs[index][1], jobs[index][0]});
            index++;
        }
        
        if (!pq.empty()) {
            auto [duration, startTime] = pq.top();
            pq.pop();

            time += duration;
            answer += time - startTime;
        } else {
            time = jobs[index][0];
        }
    }
    
    return answer / count;
}