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

 

하드디스크의 작업 처리 시간의 평균을 구하는 문제 

---

문제의 조건

 

1. 작업 처리 시작 시간과 소요 시간이 담긴 2차원 배열 jobs가 주어짐

 

2. 하드디스크는 기본적으로 먼저 들어온 순서대로 처리를 하는데 

만약 현재 처리중인 작업이 끝나지 않았는데 새로운 처리 요청이 2개 이상 들어오면

그 중 작업 소요 시간이 짧은 순서대로 처리한다. 

=> 우선순위 큐에 현재 작업시간보다 짧거나 같은 작업들을 저장하는데

작업의 소요시간이 짧은 순서로 정렬해서 저장해야 함

(여기서 함수 사용법을 몰라서 아주 많이 헤멤...)

 

3. 모든 작업이 끝나서 쉬는 상태라면 남은 작업들 중 가장 먼저 들어온 것부터 처리한다. 

 

2, 3번 과정을 반복해서 총 작업 소요 시간을 구한 뒤 작업의 갯수로 나눠서 평균 구하면 되는데

총 작업 소요시간을 구하려면 대기 시간도 구해야 한다. 

대기 시간을 구하려면

작업이 완료된 시간 - 입장 시간 

으로 계산하면 된다. (근데 처음엔 잘못 생각해서 계산식을 잘못 씀)

 

그래서 현재 작업 시작 시간을 저장할 변수와 총 소요 시간을 저장할 변수가 필요하다. 

 

---

우선순위 큐를 쓰면 되겠다까지는 쉽게 생각했는데

우선순위 큐에서 소요시간 기준 오름차순 정렬을 어떻게 하나 헤메는 바람에 시간 많이 쓴 문제 ㅠㅠ

물론 작업 소요 시간 계산도 잘못하긴 했었다...

 

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

using namespace std;

//우선순위 큐의 정렬 조건용 비교 함수 (새로운 거 배웠네용...)
struct compare
{
    bool operator()(const vector<int>& a, const vector<int>& b)
    { return a[1] > b[1]; }
};

int solution(vector<vector<int>> jobs) {
    int jobsCount = jobs.size(); //총 작업 갯수 
    //입력시간 기준으로 오름차순 정렬 
    //입력시간이 같으면 작업 소요시간 기준으로 오름차순 정렬 
    sort(jobs.begin(), jobs.end(), [](const vector<int>& a, const vector<int>& b)->bool { 
        if (a[0] < b[0])
            return true;

        if (a[0] == b[0] && a[1] < b[1])
            return true;

        return false; 
    });

    int processTime = 0; //총 소요 시간
    int endTime = 0; //작업 종료 시간 

    priority_queue<vector<int>, vector<vector<int>>, compare> nextWorks;
    int i = 0; //jobs 배열 탐색용 인덱스
    
    //원래는 jobs 배열 자체를 내림차순 정렬한 후 pop_back() 하면서 줄여나가는 방식으로 짰었으나...
    //계산식 자체를 잘못 쓴 줄 모르고 계속 안 되니까 구글링 하다 아래와 같이 수정하게 됨 
    
    //인덱스가 배열 사이즈보다 작거나 큐가 비지 않았을 동안 반복 
    while (jobs.size() > i || !nextWorks.empty())
    {
        //인덱스가 배열 사이즈보다 작고 다음 작업 시작 시간이 현재 작업 종료 시간보다 작다면
        if (jobs.size() > i && endTime >= jobs[i][0])
        {
            //우선순위 큐에 추가 후 인덱스 증가 
            nextWorks.push(jobs[i++]);

            //다른 작업이 있을 수도 있으니까 위 조건을 만족하지 않을 때까지 탐색 
            continue;
        }

        //큐가 비지 않았으면 다음 작업은 top이 되고
        vector<int> nextWork;
        if (!nextWorks.empty())
        {
            nextWork = nextWorks.top();
            nextWorks.pop();
            
            //다음 작업의 소요시간을 더해주면 작업 종료시간을 구할 수 있다. 
            endTime += nextWork[1];
            
            //총 작업 소요 시간은 대기 시간까지 포함해야 하기 때문에 
            //작업 종료 시간에서 입장 시간을 빼준 값 
            processTime += endTime - nextWork[0];
        }
        //비었으면 다음 작업은 현재 인덱스 값
        else 
        {
            nextWork = jobs[i];
            //작업을 하지는 않았으니까 시간만 갱신해준다. 
            endTime = nextWork[0];
        }

    }

    int answer = processTime / jobsCount;

    return answer;
}