[프로그래머스] 디스크 컨트롤러(C++)

Eunyoung Han·2022년 10월 21일

알고리즘 프로그래머스 힙

https://school.programmers.co.kr/learn/courses/30/lessons/42627
프로그래머스 스킬체크 레벨3 풀다가 여유부리는 바람에 이 문제를 다 못풀었다 하하

해결 방법

맨 처음 떠오른 것은 회의실 배정 문제였다.
하지만 모든 회의를 배정하지 않아도 된다는 점이 이 문제와 달라서, 다른 방법을 떠올렸어야 했다.
그렇지만 이 문제에서 떠올린 생각은, 가장 빨리 끝나는 작업부터 배정해야겠다였다.
또 고려해야할 점은, 현재 요청이 들어온 작업 중에서 라는 점이다.

👉 "지금 현재 요청이 들어온 작업 중에서 가장 빨리 끝나는 작업을 배정하자"는 아이디어가 떠올랐다.

요청 순서대로 작업(jobs) 정렬하기

먼저 입력받은 작업을 요청 시간 순서대로 정렬해야할 필요가 있다고 생각했다.
- 처음엔 vector 안에서 정렬하면 되려나? 하는 생각이 들었는데,
  작업 선택의 후보군(내가 구현한 코드에서 readyQ)에 들어갔는지 따로 표시를 해야될 것 같아서 귀찮았다...
- 내가 정한 우선순위대로 항상 정렬해주는건 역시 우선순위큐 이겠거니, 싶어서 우큐로 구현

우선순위 큐 커스텀하기

입력받은 작업을 요청 순서대로 정렬하기 위해서 작업을 모두 우선순위 큐에 넣어줄 것이다.
그렇다면 요청 순서대로 정렬하도록 cmp 구조체를 정의해야한다.

struct cmp{
  bool operator()(pii& a, pii& b){
      if(a.first == b.first) return a.second>b.second;
      return a.first>b.first;
  }  
};

요청이 빨리 들어온 순서대로, 만약 요청한 시간이 같다면 작업시간이 적게 걸리는 순서대로 정렬했다.
이제 작업들을 우큐 안에 넣어 정렬했으니, 우큐 안에서 잘 꺼내기만 하면 된다.

현재 요청이 들어온 작업 찾기 (readyQ)

지금 현재 시간(time)에, 요청이 들어온 작업 후보군을 만들어야 한다.
왜냐하면 요청이 들어온 작업들 중에 선택할 것이기 때문이다.
따라서, 현재 시간보다 먼저 요청된 (q.top().first <= time) 작업들을 골라 후보군을 만들어줬다.
운영체제 스케줄러 공부하며 배운,, ready Queue에서 이름을 따왔다 하하

작업시간이 가장 짧은 작업 찾기

readyQ 정렬

후보들 중에서 작업시간이 제일 짧은 작업을 고를 예정이므로, 후보들을 작업시간이 짧은 순서대로 정렬할 필요가 있다. 따라서 readyQ도 우선순위큐로 구현했다.

struct rcmp{
   bool operator()(pii& a, pii& b){
      if(a.second == b.second) return a.first>b.first;
      return a.second>b.second;
  }  
};

그냥 전체 작업을 요청 시간순대로 정렬했던것과는 다르게, 작업시간이 짧은 순서대로 정렬해야하므로 second 기준으로 정렬했다. 같은 경우는 그냥 먼저 요청한 친구부터~

소스 코드

큐가 비어있을 때 pop하지는 않는지 주의하며 구현하도록 하자
종료조건은 q가 비어있고 && readyQ가 비어있고 && 현재 진행중인 작업도 없을 때 이다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
#define pii pair<int,int>

struct cmp{
  bool operator()(pii& a, pii& b){
      if(a.first == b.first) return a.second>b.second;
      return a.first>b.first;
  }  
};

struct rcmp{
   bool operator()(pii& a, pii& b){
      if(a.second == b.second) return a.first>b.first;
      return a.second>b.second;
  }  
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    priority_queue<pii, vector<pii>, cmp> q;
    priority_queue<pii, vector<pii>, rcmp> readyQ;
    for (int i = 0; i < jobs.size(); i++) {
        q.push({ jobs[i][0],jobs[i][1] });
    }

    bool is_empty = true;
    int time = 0; pii cur_process = { -1,-1 }; //요청시작시간, 끝나야하는시간
    while (q.size() || readyQ.size() || !is_empty) {
        if (!is_empty) {
            if (cur_process.second == time) {
                answer += (time - cur_process.first);
                is_empty = true;
            }
        }
        if (is_empty) {
            if (q.size()) {
                while (q.size() && q.top().first <= time) {
                    auto cur = q.top(); q.pop();
                    readyQ.push(cur);
                }
            }
            if (readyQ.size()) {
                auto cur = readyQ.top(); readyQ.pop();
                cur_process = { cur.first, time + cur.second };
                is_empty = false;
            }
        }
        time++;
    }
    return answer / jobs.size();
}