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

디스크 컨트롤러

첫 번째 풀이

---

• 코드 의도: 분류는 힙인데.. 뭔지 모르겠다.,
• 결과: 정확성 100점 (20/20), 총 100점

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

using namespace std;

bool compare(vector<int> v1, vector<int> v2)
{
    if (v1[1] == v2[1])
        return v1[0] < v2[0];

    return v1[1] < v2[1];
}

int solution(vector<vector<int>> jobs)
{
    sort(jobs.begin(), jobs.end(), compare);

    bool* completed = new bool[jobs.size()];
    for (int i = 0; i < jobs.size(); i++)
        completed[i] = false;

    int lastCompletedTime = 0;
    int sumOfElapsedTime = 0;

    for (int i = 0; i < jobs.size(); i++)
    {
        int curProcessIndex = -1;
        int earliestReqTime = 1001;
        int earliestReqIndex = -1;

        // 다음 작업을 찾는다.
        // 만약 당장 시작할 수 있는 작업이 없는 경우, 남은 작업 중 가장 먼저 요청된 작업을 찾는다.
        for (int ji = 0; ji < jobs.size(); ji++)
        {
            if (completed[ji])
                continue;

            if (jobs[ji][0] < earliestReqTime)
            {
                earliestReqTime = jobs[ji][0];
                earliestReqIndex = ji;
            }

            if (jobs[ji][0] > lastCompletedTime)
                continue;

            completed[ji] = true;

            curProcessIndex = ji;
            break;
        }

        if (curProcessIndex != -1)
        {
            sumOfElapsedTime += jobs[curProcessIndex][1] + (lastCompletedTime - jobs[curProcessIndex][0]);
            lastCompletedTime += jobs[curProcessIndex][1];
        }
        else
        {
            int breakTime = earliestReqTime - lastCompletedTime;
            completed[earliestReqIndex] = true;

            sumOfElapsedTime += jobs[earliestReqIndex][1] + earliestReqTime - jobs[earliestReqIndex][0];
            lastCompletedTime += jobs[earliestReqIndex][1] + breakTime;
        }
    }

    delete[] completed;
    return sumOfElapsedTime / jobs.size();
}

---

자료구조에서 힙을 배우긴 했었지만..
어떻게 쓸지를 몰라 그냥 무작정 풀었다.

역시 나 스스로가 많이 부족하다고 느꼈다.

최종 풀이

---

• 코드 의도: 좋아보이는 풀이를 보고 배끼자, (Priority Queue, Template, Iterator)
• 결과: 정확성 100점 (20/20), 총 100점

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

using namespace std;

struct CompareProcessTime
{
    bool operator()(const vector<int>& v1, const vector<int>& v2)
    {
        // 우선순위 큐는 큰 것 순서대로 정렬하기 때문에,
        // 오름차순으로 만들어주기 위해서는 정렬 순서를 반대로
        return v1[1] > v2[1];
    }
};

struct CompareReqTime
{
    bool operator()(const vector<int>& v1, const vector<int>& v2)
    {
        return v1[0] < v2[0];
    }
};

int solution(vector<vector<int>> jobs)
{
    priority_queue<vector<int>, vector<vector<int>>, CompareProcessTime> pq;

    sort(jobs.begin(), jobs.end(), CompareReqTime());
    auto it = jobs.begin();

    int sumOfElapsedTime = 0;
    int curTime = jobs[0][0];

    while ((it != jobs.end()) || !pq.empty())
    {
        while ((it != jobs.end()) && ((*it)[0] <= curTime))
        {
            pq.push((*it));
            it++;
        }

        if (!pq.empty())
        {
            curTime += pq.top()[1];
            sumOfElapsedTime += (curTime - pq.top()[0]);
            pq.pop();
        }
        else
        {
            curTime = (*it)[0];
        }
    }

    return sumOfElapsedTime / jobs.size();
}

다른 분들의 풀이를 보다가, 제일 깔끔해보이는 코드가 이거였다.
CPP의 Priority Queue, Template, Iterator를 이번에 배웠다.

Priority Queue는 기본적으로 내림차순으로 정렬을 하기에,
오름차순으로 정렬되는 Compare 구조체를 만들 때 리턴을 반대로 줘야했다.
우선순위가 더 높은 것에 true를 리턴해줘야 했다.

Compare 구조체도 사실 이번에 알았다.
기존에는 첫 번째 풀이처럼 Compare 함수를 만들어 넣었었는데,
괄호 연산자를 재정의하는 구조체는 이번에 처음 써보았다.

Template은 모두의 코드에서 공부했다.
궁금한 것들이 죄다 있어서 유익했다.

Iterator는 C#랑 비슷한 것 같은데,
사실 C#에서도 별로 써본적이 없어서.. ㅎㅎ..
더 공부해봐야 할 것 같다.

Container Adapter? 라는 것도 잘 와닿지않는다.
마찬가지로 더 공부해야겠다..