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

디스크 컨트롤러

---

1. 이해하기

• 하드디스크는 한 번에 하나의 작업만 수행할 수 있다.
• 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리할때 평균을 구하는 문제.

---

2. 구현하기

• 우선순위 큐를 이용하여 처리 시간이 가장 짧은 것부터 처리하게 한다.

  • 이때 큐를 이용하면 원하는 위치의 삭제가 힘드니 우선순위 큐의 결과를 벡터에 담는다.

  priority_queue<pair<int,int>> pq;
  for(int i = 0; i < jobs.size(); i++)
      pq.push({-jobs[i][1],jobs[i][0]});
  vector<pair<int,int>> job;
  for(int i = 0; i < jobs.size(); i++) {
      job.push_back(pq.top());
      pq.pop();
  }

• 시간과 일의 시작시간을 비교하여 시작시간이 적거나 같은 경우에 그 일을 처리한다.

  • 아무일도 시작할 수 없을 때는 시간을 증가시켜준다. 디스크가 비어있는 시간이 있을 수도 있기 때문이다.

  int time = 0;
  while(job.size() > 0) {
      for(int i = 0; i < job.size(); i++) {
          if(time >= job[i].second) {
              time += -job[i].first;
              answer += time-job[i].second;
              job.erase(job.begin()+i);
              break;
          }
          if(i == job.size()-1) time++;
      }
  }

---

3. 전체 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue<pair<int,int>> pq;
    for(int i = 0; i < jobs.size(); i++)
        pq.push({-jobs[i][1],jobs[i][0]});
    vector<pair<int,int>> job;
    for(int i = 0; i < jobs.size(); i++) {
        job.push_back(pq.top());
        pq.pop();
    }

    int time = 0;
    while(job.size() > 0) {
        for(int i = 0; i < job.size(); i++) {
            if(time >= job[i].second) {
                time += -job[i].first;
                answer += time-job[i].second;
                job.erase(job.begin()+i);
                break;
            }
            if(i == job.size()-1) time++;
        }
    }
    return answer/jobs.size();
}