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

문제

문제: 프로그래머스-디스크컨트롤러

주의

• 문제를 잘 읽어야한다
• 작업하는 것이 없는 경우 나머지 작업들중 가장 시작이 빠른 작업 진행

문제 해결 아이디어

• 전제가 아무것도 없는 경우 가장 먼저 작업하는 것을 실행하기에 배열을 sort해야함
  • sort하는 경우 시작 시간이 같으면 시간이 더 오래걸리는 순으로 소팅
• 우선순위 큐에서 정렬하는 기준은 소요 시간이 가장 긴것을 기준으로 정렬
  • 왜? 그래야 빨리 끝냄 오래된것 먼저 해결~
• 변수 - 작업 여부관련 변수(idx), 시작 시간 판별 변수(time)
• idx가 jobs보다 작거나 pq가 비어있지 않은 경우 진행 가능
  • 만약 시작 시간이 현재 시간보다 작거나 같고 (AND) idx가 jobs크기보다 작으면
    • 큐에 삽입 & idx++ 계속 진행
  • 작업 시작 시간이 현재 시간보다 크면 작업 시간이 큰것 부터 실행 단 비어있을때까지
    • 첫번째 값 time+=큐의 첫번째 진행시간
    • answer = answer+ (time + 큐의 진행시간) - 큐의 시작시간
      즉, answer+=time-큐의 시작시간
  • 큐 비어있는데 아직 작업 완료 안함 그리고 아직 시작 시간이 먼 경우
    • time 기준을 현재 idx의 시작 시간으로 변경

코드

#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
// 아무작업도 하고있지 않는 경우 먼저 들어온 요청 부터 작업 수행
// idea 
// 1. 실행순으로 입력값을 sort한다 만약 시작 시간이 같으면 진행시간이 더 짧은걸루
// 2. 우선순위 큐 조건에서 실행시간이 짧은 것 먼저 pop
// 
bool jobscompare(vector<int> a, vector<int> b){
    if(a[0]==b[0]){
        return a[1]<b[1];
    }else {
        return a[0]<b[0];
    }
}
struct compare{
    bool operator()(vector<int> a, vector<int> b){
        return a[1]>b[1];
    }
};
int solution(vector<vector<int>> jobs){
    int answer=0;
    int time=0; // 현재 시간
    int idx =0; // 작업 관련 index

    sort(jobs.begin(), jobs.end(), jobscompare); 
    priority_queue<vector<int>, vector<vector<int>>, compare> pq;
    while(idx<jobs.size()||!pq.empty()){
        if(idx<jobs.size()&&time>=jobs[idx][0]){
            pq.push(jobs[idx]);
            idx++;
            continue;
        }
        if(!pq.empty()){
            vector<int> tmp = pq.top();
            time+=tmp[1];
            answer+=time-tmp[0];
            pq.pop();
        } else {
            // pq가 비어있으면서 다음 값이 있는데 엄청 멀리 있는경우 time을 멀리있는 작업의 시작시간으로 설정 
            time=jobs[idx][0];
        }
    }
    return answer/jobs.size();
} 
int main(){
    vector<vector<int>> jobs{{0,3},{1,9},{2,6}};
    int ans = solution(jobs);
    cout<<ans;
}

인증

배운점

• 문제를 잘 읽자 이번에는 아무것도 없으면 먼저 시작하는것부터 시작한다를 빼먹어서 삽질좀함
• priority_queue할때 맨마지막 비교 관련 함수는 구초체로 선언해야한다