[프로그래머스] 힙(Heap) > 디스크 컨트롤러

https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

 

 

처음에는 dfs 로 풀었는데 시간초과가 떳다.

힙 문제니까 priority_queue를 사용하면 되겠다 까지는 알겠는데

소요시간, 대기시간을 다 고려해야하니까 어떤 기준으로 정렬이 되도록 해야하는지를 모르겠었다.

[풀이방법]

1. 요청시간 (job[0]) 을 기준으로 정렬을 하고,

2. time 에 실행할 수 있는 프로세스들을 pq에 넣는다.

- pq 내에서 짧은 실행시간 (job[1]) 순으로 정렬이된다.

- 실행시간순으로 정렬을 해도 되는 이유는

   : 최저 평균=총합이 최소 와 같고, 최소 총합 시간을 구하란거는 시간이 비었을 때 쌓여있는 태스크 중에서 소요시간이 가장 짧은 태스크부터 처리하라는 것과 같습니다. 왜냐하면 선택한 태스크의 소요시간만큼, 쌓여있던 다른 태스크의 소요시간이 다 같이 늘어나는 셈이기 때문입니다. 대기중인 태스크가 5개라면 2초*4개만큼 늘어나는것 보다는 1초*4개만큼 늘어나는게 낫겠죠

 

3-1. pq가 비어있지 않다면

- 하나씩 빼서 time 에 프로세스의 실행시간을 + 해준다.

- answer 에 프로세스의 실행시간 + 대기시간을 더해준다.

 

3-2. pq가 비어있다면

 - 그 시간에 실행할수 있는 프로세스가 없는 것이므로 다음 프로세스의 요청시간으로 time 을 업데이트해준다.

- 다음 프로세스가 요청하기 전까지 아무런 액션이 없을 것이므로, 다음 프로세스 요청시간으로 점프를 해주는 것이다.

 

[전체 코드]

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct cmp {
    bool operator()(vector<int> a, vector <int> b) {
        return a[1] > b[1];
    }
};


int solution(vector<vector<int>> jobs) {
    int answer = 0;
    // 시작시간 기반 정렬
    sort(jobs.begin(), jobs.end());
    
    // 소요시간 기반 정렬
    priority_queue <vector <int>, vector <vector<int>> , cmp> pq;
    
    int cnt = 0;
    int time = 0;
    
    while(cnt < jobs.size() || !pq.empty()) {
        // time 에 수행할 작업이 있다면 계속 pq 에 넣음
        if(jobs.size() > cnt && time >= jobs[cnt][0]) {
            pq.push(jobs[cnt++]);
            continue;
        } // 작업목록이 있다면 수행시간이 작은 것부터 수행
        if(!pq.empty()) {
            time += pq.top()[1];
            answer += time - pq.top()[0];
            pq.pop();
        } // 작업할 요소가 없다면 다음 작업으로 넘어감
        // 다음 작업 시작시간으로 세팅
        else {
            time = jobs[cnt][0];
        }
    }
    return answer / jobs.size();
}

 

 

priorty_queue 정렬방법

struct cmp {
    bool operator()(vector<int> a, vector <int> b) {
        return a[1] > b[1];
    }
};

// 두번쨰 인자가 작은 순서부터 들어가고 나옵니다.
 priority_queue <vector <int>, vector <vector<int>> , cmp> pq;