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

 

문제

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

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

 

 

내 풀이

 

솔직히 반신반의하며 방향을 설정해서 풀었는데 운이 좋아서 맞았다.

1) jobs를 들어온 순서대로 정렬하였으며 (job[0]을 오름차순으로)

2) while 문을 전체 job들이 모두 빠져나올 때까지 돌렸다. (job 하나가 완료될 때 마다 finishCount가 올라감)

3. while문 내에서는 

3-1. 현재 시각 이하의 모든 Job들을 우선순위 Queue에 넣어준다(now라는 우선순위 큐)

3-2. 우선 순위 큐가 비어있다면, 그 다음으로 들어올 Job을 우선순위 큐에 넣어준 후, Job이 들어오는 시간으로 현재 시간을(time)을 갱신한다.

(같은 시간에 들어오는 모든 Job들을 넣어주기)

4. 우선 순위 큐에서 Job 하나를 뺀다. (걸리는 시간이 가장 짧은 것. 걸리는 시간이 같다면 들어온 순서가 빠른 것.)

5. 뺀 Job이 걸리는 시간만큼 time을 갱신한다.

6. 뺸 Job이 스케줄러에 들어온 시점부터 지금까지 얼마나 걸렸지를 측정하여 answer에 담는다.

7. pop()한다. 

8. while문이 끝나고 모든 Job들이 완료되면, answer을 Job 개수로 나눠주고 (int)를 씌워 정수로 반환한다.

 

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

using namespace std;

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

bool cmp2(vector<int> a, vector<int> b)
{
    if (a[1] == b[1])
        return a[0] < b[0];
    return a[1] < b[1];
}

int solution(vector<vector<int>> jobs) {
    
    int answer = 0;
    int finishCount = 0;
    int time = 0;
    int jobsIndex = 0;
    vector<vector<int>> now;
    
    sort(jobs.begin(), jobs.end(), cmp);

    while(finishCount < jobs.size())
    {
        if(jobsIndex < jobs.size() && jobs[jobsIndex][0] <= time){ //time 이하들 다 넣어주기
            while (jobsIndex < jobs.size() && jobs[jobsIndex][0] <= time)
            {
                now.push_back(jobs[jobsIndex]);
                //cout << "insert1 " << jobs[jobsIndex][0] << endl;
                jobsIndex++;
            }
        }
        
        else if(now.empty()) //time 이하가 없고 now가 비어있으면
        {
            time = jobs[jobsIndex][0]; //시간 이동 후 같은 시간 넣어주기
            while (jobsIndex < jobs.size() && jobs[jobsIndex][0] == time)
            {
                now.push_back(jobs[jobsIndex]);
                //cout << "insert2 " << jobs[jobsIndex][0] << endl;
                jobsIndex++;
            }
        }
        sort(now.begin(), now.end(), cmp2);
        time += now[0][1]; // 끝난 기점으로 지금 시간 갱신
        answer += (time - now[0][0]); // 지금 시간에서 시작 시간 빼서 더하기
        //cout << "now " << now[0][0] << " time "<< time << endl;
        now.erase(now.begin() + 0);
        finishCount++;
    
    }
    
    return ((int)(answer / jobs.size()));
}

 

고쳐야할 점

1. vector<int>를 받는 우선순위 큐를 구현하지 못해서 vector<vector<int>>를 사용하고 매번 정렬하는 방식을 택했다.

아직 다양한 자료형을 받는 우선 순위 큐 구현이 자유롭지 못한 것 같다.

 

2. 내가 할 수 있는 최대한의 풀이라고 생각해서 풀었지만, 정답이라고 확신하며 풀지는 않았다.

이런 경우에 어떻게 더 좋은 판단을 할 수 있을지에 대해 생각해보아야한다.