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

✅ LV.3

📌 Heap

✏️ 최종 솔루션

⭐️ 우선순위 큐

1. 요청 시점이 빠르고 길이가 짧은 디스크 순으로 우선순위 큐에 모든 디스크 넣기
2. 현재 실행 중인 디스크의 시작 시간과 끝 나는 시간을 저장해두기
3. 큐에 저장된 디스크 중에 요청 시점과 현재 실행 중인 디스크가 끝나는 시점보다 작거나 같으면 대기 큐에 넣기
   ❗️ 대기 큐는 실행 시간이 짧은 순으로 오름차순 정렬
4. 새로운 디스크 시작하기
   1) 대기 큐가 비어있다면 요청 시점이 빠른 순으로 정렬된 기본 큐의 top을 실행시키기
   ➡️ 대기한 시간이 없기 때문에 시작 시간 = 요청 시점 , 종료 시점 = 시작 시간 + 실행 시간 으로 갱신
   2) 대기 큐의 top을 실행시키기
   ➡️ 대기한 시간이 있기 때문에 시작 시간 = 요청 시점 , 종료 시점 = 현재 시점 + 실행 시간 으로 갱신
   ❗️ 실행시킬 때마다 answer 갱신

📌 self feedback

히프라는데 어쩌라는지 모르겠어서 얼레벌레 구현했다. 프로그래머스에서 요구하는 히프 문제는 우선순위 큐 활용 문제인듯

• 대기하는 디스크가 없으면 요청 시점이 빠른 순으로 실행해야 해서 인덱스를 따로 관리해야하나 싶었지만 우선순위 큐를 두 개 돌려서 풀이가 가능했다.
• 현재 디스크의 시작 시간과 종료 시간의 범위 내에서 다음으로 갈 수 있는 디스크를 또다른 우선순위 큐로 관리하는 발상이 도움이 되었다.

이런 문제가 또 나오면 어찌할지 모르겠엄,,

✏️ 최종 code

#include <queue>
#include <vector>
#include <iostream>

using namespace std;

struct task {
    int st;
    int len;
};

struct cmp1 {
    bool operator()(task t1, task t2) {
        if(t1.st==t2.st) {
            return t1.len>t2.len;
        }
        return t1.st>t2.st;
    }
};

struct cmp2 {
    bool operator()(task t1, task t2) {
        return t1.len>t2.len;
    }
};

int solution(vector<vector<int>> jobs) {
    int answer = 0;
    // 요청 순서 빠른 순(요청 시점,시간)
    priority_queue<task,vector<task>,cmp1> pq_early;
    // 시간 짧은 순
    priority_queue<task,vector<task>,cmp2> pq_short;

    for(int i=0;i<jobs.size();i++) {
        pq_early.push({jobs[i][0],jobs[i][1]});
    }
    
    int cnt=0, e=0;

    while(1) {
        if(pq_early.empty() && pq_short.empty()) break;
        int cur,idx,len;
        while(!pq_early.empty()) {
            cur=pq_early.top().st;
            
            if(cur>e) break;
            
            len=pq_early.top().len;
            
            pq_early.pop();
            pq_short.push({cur,len});
        }

        int next;
        // 새로운 task 시작
        if(pq_short.empty()) {
            // 요청 빠른 것 시작
            next=pq_early.top().st;
            len=pq_early.top().len;
            pq_early.pop();
            
            cnt=next;
            e=cnt+len;
            
            answer+=(e-cnt);
        }
        else {
            // 대기 큐에 있는 것 넣기
            next=pq_short.top().st;
            len=pq_short.top().len;
            pq_short.pop();
            
            cnt=next;
            e+=len;
            
            answer+=(e-cnt);
        }

    }
    
    return answer/jobs.size();
}