디스크 컨트롤러
문제 링크 : 디스크 컨트롤러
문제 설명
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.
- 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.
- 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
- 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
- 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.
예를 들어
- 0ms 시점에 3ms가 소요되는 0번 작업 요청
- 1ms 시점에 9ms가 소요되는 1번 작업 요청
- 3ms 시점에 5ms가 소요되는 2번 작업 요청와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 다음과 같습니다.
이 요청을 우선순위 디스크 컨트롤러가 처리하는 과정은 다음 표와 같습니다.
| 시점 | 하드디스크 | 대기 큐 | 디스크 컨트롤러 |
|---|---|---|---|
| 0ms | [] | ||
| 0ms | [[0번, 0ms, 3ms]] | 0번 작업 요청을 대기 큐에 저장 | |
| 0ms | 0번 작업 시작 | [] | 대기 큐에서 우선순위가 높은 0번 작업을 꺼내서 작업을 시킴 |
| 1ms | 0번 작업 중 | [[1번, 1ms, 9ms]] | 1번 작업 요청을 대기 큐에 저장 |
| 3ms | 0번 작업 완료 | [[1번, 1ms, 9ms]] | |
| 3ms | [[1번, 1ms, 9ms], [2번, 3ms, 5ms]] | 2번 작업 요청을 대기 큐에 저장 | |
| 3ms | 2번 작업 시작 | [[1번, 1ms, 9ms]] | 대기 큐에서 우선순위가 높은 2번 작업을 꺼내서 작업을 시킴 |
| 8ms | 2번 작업 완료 | [[1번, 1ms, 9ms]] | |
| 8ms | 1번 작업 시작 | [] | 대기 큐에서 우선순위가 높은 1번 작업을 꺼내서 작업을 시킴 |
| 17ms | 1번 작업 완료 | [] |
모든 요청 작업을 마쳤을 때 각 작업에 대한 반환 시간(turnaround time)은 작업 요청부터 종료까지 걸린 시간으로 정의합니다. 위의 우선순위 디스크 컨트롤러가 처리한 각 작업의 반환 시간은 다음 그림, 표와 같습니다.
| 작업 번호 | 요청 시각 | 작업 종료 시각 | 반환 시간 |
|---|---|---|---|
| 0번 | 0ms | 3ms | 3ms(= 3ms - 0ms) |
| 1번 | 1ms | 17ms | 16ms(= 17ms - 1ms) |
| 2번 | 3ms | 8ms | 5ms(= 8ms - 3ms) |
우선순위 디스크 컨트롤러에서 모든 요청 작업의 반환 시간의 평균은 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입니다.
입출력 예
| jobs | return |
|---|---|
| [[0, 3], [1, 9], [3, 5]] | 8 |
풀이 방법
- 시간이 변해감에 따라서 값을 넣으면서 정렬을 주기적으로 해야 되기 때문에, 우선순위 큐를 통해서 풀 생각을 했고, 작업 시간, 작업 요청 시각, 작업의 번호에 따라 정렬을 해야 되기 때문에 이를 관리하기 위해 구조체를 사용했다.
- 우선순위 큐를 순서대로 하기 위해 구조체를 사용해서 사용자 지정 비교를 만들었다.
- 먼저, 시간별로 우선순위 큐에 넣으면서 모든 요청을 우선순위 큐에 넣고자 했고, 현재 시간보다 작은 모든 작업을 우선순위 큐에 넣고, 우선순위가 가장 높은 작업을 실행해주었다. 우선순위 큐가 비었는데, 작업 시작 시간보다 현재 시간이 작은 경우 무한 루프에 빠질 가능성이 있기 때문에 해당 경우는 현재 시간을 작업 시작 시간으로 바꿔주었다. 모든 작업을 우선순위 큐에 넣었다면, 남은 것들을 순차적으로 실행시켜주면서 현재 시간과 시작 시간의 차를 구해서 정답에 더하는 식으로 문제를 풀었다.
-> 해당 문제 풀이 방법은 처음에 모든 jobs를 정렬해줘야 하기 때문에O(NlogN)의 시간복잡도와 jobs를 순회하면서 우선순위 큐에 삽입하기 때문에O(NlogN)의 시간복잡도가 걸릴 것으로 보이고, N은 최대 500이기 때문에 알맞은 알고리즘으로 보인다.
구현
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct job {
int time;
int start;
int idx;
};
struct Compare {
bool operator()(const job& a, const job& b) {
if (a.time != b.time) {
return a.time > b.time;
}
if (a.start != b.start){
return a.start > b.start;
}
return a.idx > b.idx;
}
};
int solution(vector<vector<int>> jobs) {
int answer = 0;
int curIndex = 0, curTime = 0;
priority_queue<job, vector<job>, Compare> PQ;
// jobs 정렬
sort(jobs.begin(), jobs.end(), [](vector<int>& a, vector<int>& b){
return a[0] < b[0];
});
// 시간별로 우선순위큐에 넣으면서 모든 요청 우선순위 큐에 넣기
while(curIndex < jobs.size()){
// 만약, 우선순위 큐가 비었는데, 작업 시작 시간보다 현재 시간이 작은 경우
if(PQ.empty() && jobs[curIndex][0] > curTime){
curTime = jobs[curIndex][0];
}
// 현재 시간보다 작은 모든 작업 큐에 넣기
while(curIndex < jobs.size() && jobs[curIndex][0] <= curTime){
PQ.push({jobs[curIndex][1], jobs[curIndex][0], curIndex});
curIndex++;
}
// 우선순위가 가장 높은 작업 실행하기
job curJob = PQ.top(); PQ.pop();
curTime += curJob.time;
answer += curTime - curJob.start;
}
// 우선순위 큐에 남은 것들 순차적으로 실행시키기
while(!PQ.empty()){
job curJob = PQ.top(); PQ.pop();
curTime += curJob.time;
answer += curTime - curJob.start;
}
return answer / jobs.size();
}
게임 개발자를 향해..