[프로그래머스 42627]디스크 컨트롤러

문제링크

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

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

 

문제난이도

Level3

 

문제풀이

1. jobs 벡터이 입력된 정보를 정렬해준다 --> [작업요청시간, 작업소요시간]

   ⓐ 작업요청시간 기준으로 오름차순 정렬

   ⓑ 작업요청시간이 같을 경우, 작업에 소요되는 시간을 기준으로 오름차순 정렬

2. jobs 벡터에서 수행할 작업을 꺼낸다

3. 2번에서 꺼낸 작업이 시작하는 시간(startTime)을 계산한다

   - 이전작업이 끝난 시간(최초 작업이라면 끝난시간은 0일 것이다)을 기준 = endTime

       ⓐ 요청시간이 endTime과 같거나 이전인 경우, 이전 작업이 끝난 시간이 시작시간(startTime)이 된다

       ⓑ 요청시간이 endTime 이후인 경우, 작업요청이 들어온 시간이 시작시간(startTime)이 된다

4. 2번에서 꺼낸 작업이 끝나는 시간(endTime)을 계산한다

   - 작업을 시작한 시간 + 작업소요시간

5. 2번에서 꺼낸 작업이 수행되는 시간동안 요청이 들어온 작업들을 담는다

6. 2번에서 꺼낸 작업이 종료 될 때까지 걸린 총 시간을 누적해준다

   - 작업이 종료된 시간에서 0 시간부터 대기하지 않은 시간을 빼면된다.

     즉, 0 시간 부터 작업요청시간 까지는 작업이 대기하거나 수행된 시간이 아니다

     따라서, 작업이 끝난시간 - 작업요청시간 계산을 하면 총 소요된 시간을 구할 수 있다

     각 작업마다 구한 값들을 누적합을 해준다

7. 종료된 작업은 제외시킨다

8. 5번에서 구한 작업들은 모두 시작할 준비가 된 작업들이므로

    구한 작업들을 소요시간 기준으로 오름차순한다

9. 모든 작업이 수행을 마칠때까지 2번부터 반복한다

10. 누적합을 수행한 작업의 갯수로 나눈다(소수점은 버린다)

 

테스트케이스

(프로그래머스의 질문하기를 통해 얻은 테스트케이스들 입니다)

//INPUT                                      //OUTPUT
 
//{{0, 3}, {1, 9}, {2, 6}}                   //9 
//{{0, 4}, {0, 3}, {0, 2}, {0, 1}}           //5 
//{{0, 9}, {0, 4}, {0, 5}, {0, 7}, {0, 3}}   //13 
//{{1, 9}, {1, 4}, {1, 5}, {1, 7}, {1, 3}}   //13 
//{{0,3}}                                    //3 
//{{5,3}}                                    //3 
//{{0,3},{0,3}}                              //4 
//{{0,3},{4,4}}                              //3 
//{{0,3},{1,4},{2,5}}                        //6 
//{{0,3},{1,1},{3,5}}                        //4 
//{{0, 5}, {1, 2}, {5, 5}}                   //6 
//{{0, 3}, {1, 9}, {500, 6}}                 //6
//{{0, 3}, {1, 9}, {500, 1}}                 //5

 

 

 

소스코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool comp(pair<int, int>& a, pair<int, int>& b) {
    return a.second < b.second;
}
 
int solution(vector<vector<int>> jobs) {
    int answer = 0;
    int workCnt = jobs.size();
    vector<pair<int, int>> readyQ;
    sort(jobs.begin(), jobs.end()); //job이 들어온 시간 오름차순 중, 작업 소요시간 오름차순 정렬
 
    int startTime = 0;
    int endTime = 0;
    while (readyQ.size() > 0 || jobs.size() > 0) {
        //
        if (readyQ.size() == 0) {
            readyQ.push_back(make_pair(jobs[0][0], jobs[0][1]));    //최초 작업 적재
            jobs.erase(jobs.begin());  //적재된 작업 삭제 
        }
        //수행할 작업의 시작,종료시간 계산
        if (endTime >= readyQ[0].first) {
            startTime = endTime;
        }
        else {
            startTime = readyQ[0].first;
        }
        endTime = startTime + readyQ[0].second;
 
        //작업 수행 중, 들어오는 job 적재
        while (jobs.size() > 0 && jobs[0][0] <= endTime) {
            if (endTime >= jobs[0][0]) {    //작업 수행중 적재가 가능한 job 체크
                readyQ.push_back(make_pair(jobs[0][0], jobs[0][1]));
                jobs.erase(jobs.begin());
            }
        }
 
        answer = answer + (endTime - readyQ[0].first);
        readyQ.erase(readyQ.begin());   //종료된 작업 삭제
        sort(readyQ.begin(), readyQ.end(), comp);   //수행 가능한 작업중 가장 짧은 작업순으로 정렬
    }
 
    return answer / workCnt;
}