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

문제 링크

1. 문제 접근 과정🧐

1. 우선순위에 따라서 디스크를 처리해야 하므로 우선순위 큐를 활용
2. 처리해야 할 작업을 들어온 시간에 따라 정렬(현재 시간보다 시작 시간이 빠른 작업만 처리 가능하기 때문)
3. 큐가 비어있다면 현재 시간을 다음 작업 시작 시간으로 갱신하고 작업 시작 시간이 그보다 작은 작업을 큐에 추가
4. 큐가 비지 않았다면 큐에서 한 작업을 처리하고 현재 시간을 처리 시간을 더해 갱신하고 작업 시간이 그보다 작은 작업을 큐에 추가
5. 한 작업을 처리할 때 처리 시간을 (현재 시간 - 시작 시간)으로 갱신
6. 처리한 작업이 모든 작업 수와 같은 때까지 3-5번을 반복
7. 처리 시간을 모든 작업 수로 나누면 정답
   
   

2. 시행착오🤯

• 처음에 현재 시간과 도착 시간을 고려하지 않고 모든 작업을 큐에 넣어 처리하여 예외가 있어 실패했다.

  • 현재 시간보다 도착 시간이 작은 작업만 큐에 넣어야 한다.
  • 도착 시간이 현재 시간보다 늦어지면 대기 시간(Idle Time)이 생기는 데 이를 고려하지 못한다.

  

• 오답 코드

#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

struct compare
{
    bool operator () (tuple<int, int, int> t1, tuple<int, int, int> t2){
        if(get<0>(t1) == get<0>(t2) && get<1>(t1) == get<1>(t2)) return get<2>(t1) > get<2>(t2);
        else if(get<0>(t1) == get<0>(t2)) return get<1>(t1) > get<1>(t2);
        else return get<0>(t1) > get<0>(t2);
    }   
};

int solution(vector<vector<int>> jobs) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, compare> pq;
    for(int i = 0; i < jobs.size(); i++) pq.push({jobs[i][1], jobs[i][0], i});
    vector<int> return_time(jobs.size(), 0);
    int cur = 0;
    while(!pq.empty()){
        int w = get<2>(pq.top());
        int t = get<0>(pq.top());
        int s = get<1>(pq.top());
        pq.pop();
        cur += t;
        return_time[w] = cur;
    }
    int total = 0;
    for(int i = 0; i < jobs.size(); i++) total += return_time[i] - jobs[i][0];
    return total / jobs.size();
}

3. 개선한 코드😄

• 현재 시간과 도착 시간을 고려하여 작업을 처리하여 해결
  
• 정답 코드

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

using namespace std;

struct compare
{
    bool operator () (tuple<int, int, int> t1, tuple<int, int, int> t2){
        if(get<0>(t1) == get<0>(t2) && get<1>(t1) == get<1>(t2)) return get<2>(t1) > get<2>(t2);
        else if(get<0>(t1) == get<0>(t2)) return get<1>(t1) > get<1>(t2);
        else return get<0>(t1) > get<0>(t2);
    }   
};

int solution(vector<vector<int>> jobs) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, compare> pq;
    sort(jobs.begin(), jobs.end(), [](vector<int>& v1, vector<int>& v2){
        return v1[0] < v2[0];
    });
    int cur = 0, total = 0, idx = 0, done = 0;
    while(done < jobs.size()){
        if(!pq.empty()){
            int s = get<1>(pq.top());
            int l = get<0>(pq.top());
            pq.pop();
            cur += l;
            total += cur - s;
            done++;
            while(idx < jobs.size() && jobs[idx][0] <= cur){
                pq.push({jobs[idx][1], jobs[idx][0], idx});
                idx++;
            }
        }
        else{
            cur = jobs[idx][0];
            while(idx < jobs.size() && jobs[idx][0] <= cur){
                pq.push({jobs[idx][1], jobs[idx][0], idx});
                idx++;
            }
        }
    }
    return total / jobs.size();
}

4. 회고💭

• 처음에 시뮬레이션으로 현재 시간을 올리면서 작업 처리를 생각했다가 문제의 케이스만 생각하여 모든 작업을 큐에 넣어 처리하였다가 실패했다.
• 고려해야 할 상황을 정확하게 체크해야 한다.
  • 머릿 속이나 종이에 여러 상황을 적어보면서 어떻게 되는지 생각해야 하면 도움이 될 것 같다.
• 성급하게 풀기 보다 정확하게 판단하여 푸는 것이 중요하다!