프로그래머스 LV 3 _ 디스크 컨트롤러 (C++)

 

0️⃣ 문제링크

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

1️⃣ 문제 풀이

https://astrid-dm.tistory.com/431

https://mungto.tistory.com/15

처음에 풀던 방식으로 풀리지가 않아 결국 타임오버로 다른 블로그를 참고하였다.

위에 링크는 priority queue 를 쓰지않은 방식 아래는 사용한 방식이다.

위에 방식이 더 이해가 잘 되어 위에 방식을 참고하였다.

2️⃣ 내코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
bool compare(const vector<int>& a, const vector<int>& b)
{
    return a[1] < b[1];
}
 
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int n = jobs.size();
    int time = 0;
 
    sort(jobs.begin(), jobs.end(), compare); //업무시간 순으로 오른차순 정렬
 
    while (!jobs.empty())
    {
        for (int i = 0; i < jobs.size(); i++)  //업무시간 적은 순으로 순회하면서 
        {
            if (jobs[i][0] <= time)   // time보다 실행시간이 적거나 같은 잡 탐색
            {  //있을 경우
                time += jobs[i][1];    
                answer += time - jobs[i][0];
                jobs.erase(jobs.begin() + i);
                break;
            }  
            if (i == jobs.size()-1) //없을 경우 time증가
                time++;
 
        }
    }
 
    return answer / n;
}

3️⃣ 다른코드

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct cmp {
    bool operator()(vector<int> a, vector<int> b) {
        return a.at(1) > b.at(1);
    }
};
 
int solution(vector<vector<int>> jobs) {
    //결과 저장용 변수, 인덱스 관리용, 시간체크용
    int answer = 0, j = 0, time = 0;
    //시간에 따른 오름차순으로 정렬
    sort(jobs.begin(), jobs.end());
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq; //우선순위 큐 min heap
    //대기열이 없고 우선순위 큐가 빌때까지 반복
    while (j < jobs.size() || !pq.empty()) {
        //들어올 대기열이 남아있고, 들어올 대기열이 현재시간보다 작다면
        if (jobs.size() > j && time >= jobs[j][0]) {
            //우선순위 큐에 추가
            pq.push(jobs[j++]);
            //인덱스 증가
            //같은시간대에 다른작업이 더들어왔을 수 있으므로 다시 확인
            continue;
        }
        //큐가 비어있지 않다면
        if (!pq.empty()) {
            //시간에 이작업이 끝날때까지 걸리는 시간만큼 추가
            time += pq.top()[1];
            //작업시간에 대기 시간만큼 추가(현재시간 - 들어온 시간)
            answer += time - pq.top()[0];
            //작업이 끝났으므로 우선순위 큐에서 제거
            pq.pop();
        }
        else //큐가 비어있다면 다음작업 시간으로 넘김
            time = jobs[j][0];
    }
    return answer / jobs.size();//평균을 구해야하므로 총작업한 개수로 나눠줌
}

4️⃣ 새로 알게된 점 또는 참고한 자료

https://astrid-dm.tistory.com/431

https://mungto.tistory.com/15

우선순위 큐 특징을 찾아보던중 우선순위큐를 커스텀 정렬 하는 식을 찾아보니 구조체로 정의되어있어서 

처음에 이해가 안되었다. 찾아보니 우선순위 큐에 대한 자료구조 지식이 나에게 부족한 걸 알 수 있었다.

나중에 자료구조에 대해 확실히 공부하는 시간이 있어야 할 것 같다.