프로그래머스lv3 _ 디스크 컨트롤러

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

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

---

풀이방법

프로그래머스의 heap관련 문제다.

작업 시간이 큰게 우선순위로 작업해야 한다는 것만 알면 어렵지는 않은 문제였다.

 

로직은 다음과 같다

 

1. 현재 시각보다 작거나 같은 시작시간을 가진 값들을 priority que에다 넣는다.

2. priority que가 비어있지 않을때는 priority que의 값을 뱉는다.

3. priority que가 비어있다면 현재시각 +=1한다.

 

위의 세가지의 반복, 탈출조건은 priority que가 비어있고 주어진 jobs vector도 비었을때 이다.

---

코드

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

using namespace std;

bool compare(const vector<int>& a, const vector<int>& b)
{
    return a[0] < b[0];
}

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

int solution(vector<vector<int>> jobs) {
    int answer = 0;

    //jobs을 시간순서대로 sort
    sort(begin(jobs), end(jobs), compare);

    priority_queue<vector<int>, vector<vector<int>>, cmp> pri_que;
    int presentTime = 0;
    int allWorkTime = 0;
    int divideNum = jobs.size();
    
    while(1)
    {
        //탈출조건
        if (pri_que.empty() && jobs.size()==0)
            break;

        //현재 시각보다 작거나 같은 jobs에 값들을 pri_que에 넣는다.
        for (int i = 0; i < jobs.size();)
        {
            if (presentTime < jobs[i][0])
                break;

            //pri_que에 넣은 값들은 jobs에서 삭제해야함
            pri_que.push(jobs[i]);
            jobs.erase(jobs.begin());
        }

        //pri_que가 비어있지 않을시에 값을 뱉는다.
        if (pri_que.empty() == false)
        {
            vector<int>presentWork = pri_que.top();
            pri_que.pop();
            int startTime = presentWork[0];
            int workTime = presentWork[1];

            //현재시간 + workTime - startTime
            presentTime += workTime;
            allWorkTime += (presentTime - startTime);
        }
        //비어있다면 공백시간이므로 presentTime에 +1을 해준다.
        else
        {
            presentTime += 1;
        }
    }

    //answer 도출 allWorkTime/divideNum
    answer = allWorkTime / divideNum;

    return answer;
}

---

비교적 간단한 로직이었음에도 생각이 정리가 잘 되지 않아 생각보다 시간이 좀 걸렸다