💻 디스크 컨트롤러

분류 : Heap (힙)

사용 언어 : C++

문제 링크

🤔 문제 이해

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

해결 방안

이 문제의 포인트는 현 시간에 할 수 있는 작업이 없을시 가장 빠른 것을, 하나일 시 바로 그 작업을, 여러개일 시 가장 오래걸리지 않는 것을 작업 실행하는 것이다.

💡 문제 풀이

방법 1 )

Vector를 계속 Sort하여 가장 최적의 값을 Pop한다.

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

using namespace std;

int times = 0;	// 현 작업 시간 기록용, cmp에서 사용하기 때문에 밖으로 빼줌.

bool cmp(vector<int> a, vector<int> b) {	// sort의 정렬 방식 설정
    if (a[0] <= times && b[0] <= times) {
        // 둘 다 가능한 시간 내로 왔을 시 작업의 소요시간 기준으로 내림차순
        return a[1] > b[1];
    }
    else {
        // 둘 다 가능한 시간 외일 시 작업이 요청되는 시점으로 내림차순
        return a[0] > b[0];
    }
}

int solution(vector<vector<int>> jobs) {
    int result = 0;

    int jobs_size = jobs.size();
    // 평균 시간을 구하기 위한 초기 크기 저장

    while (jobs.size()) {
        // jobs에 원소가 없어질 때까지 반복
        sort(jobs.begin(), jobs.end(), cmp);
        //cmp의 기준에 따라 정렬

        vector<int> pop_this = jobs.back();
        // cmp에 가장 충족되는 값 복사

        if (times < pop_this[0]) {
            // 가장 충족되는 값보다 times가 작다면 times를 시간을 끌어옴
            times = pop_this[0];
        }
        else {
            // 가능한 시간이라면 작업을 실행함.
            times += pop_this[1];
            result += times - pop_this[0];	// 작업이 완료된 시간 - 작업이 신청된 시간
            jobs.pop_back();
        }
    }

    return (int)(result / jobs_size);	// 평균 작업 시간 return
}

/*
정확성  테스트
    테스트 1 〉	통과 (48.35ms, 3.97MB)
    테스트 2 〉	통과 (37.30ms, 3.98MB)
    테스트 3 〉	통과 (27.06ms, 3.96MB)
    테스트 4 〉	통과 (25.71ms, 3.98MB)
    테스트 5 〉	통과 (44.93ms, 3.85MB)
    테스트 6 〉	통과 (0.05ms, 3.97MB)
    테스트 7 〉	통과 (21.21ms, 3.96MB)
    테스트 8 〉	통과 (12.92ms, 3.97MB)
    테스트 9 〉	통과 (1.68ms, 3.98MB)
    테스트 10 〉	통과 (55.89ms, 3.98MB)
    테스트 11 〉	통과 (0.01ms, 3.96MB)
    테스트 12 〉	통과 (0.02ms, 3.96MB)
    테스트 13 〉	통과 (0.02ms, 3.98MB)
    테스트 14 〉	통과 (0.01ms, 3.96MB)
    테스트 15 〉	통과 (0.01ms, 3.97MB)
    테스트 16 〉	통과 (0.01ms, 3.97MB)
    테스트 17 〉	통과 (0.01ms, 3.96MB)
    테스트 18 〉	통과 (0.01ms, 3.96MB)
    테스트 19 〉	통과 (0.01ms, 3.94MB)
    테스트 20 〉	통과 (0.01ms, 3.97MB)

채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n^2

while을 통하여 최적의 값을 cmp를 통하여 sort 하여 모든 값을 pop할때 까지 반복

cmp는 특정 기준에 대해 오름차순으로 설정하여 vector의 top값이 최적이 값이 되도록 설정.
(vector의 pop_back()을 사용하기 위해 top이 최적의 값이 되도록 설정함.)

방법 2 )

multiset을 사용하여 정렬 방식을 설정해주고 최적의 값을 erase한다.

#include <string>
#include <vector>
#include <set>

using namespace std;

int times = 0;	// 현 작업 시간 기록용, cmp에서 사용하기 때문에 밖으로 빼줌.

struct cmp {
    // set의 정렬 방식 설정
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        if ((a.first <= times && b.first <= times) || (a.first == b.first)) return a.second < b.second;
        // 둘 다 가능한 시간 내로 왔거나 작업이 요청되는 시점이 같을 시 작업의 소요시간으로 오름차순

        return a.first <= b.first;
        // 위 조건이 아니라면 작업이 요청되는 시점으로 오름차순
    }
};

int solution(vector<vector<int>> jobs) {
    int result = 0;

    multiset <pair<int, int>> works;	
    // 정렬을 위한 multiset, {작업이 요청되는 시점, 작업의 소요시간}

    for (int i = 0; i < jobs.size(); i++) {
        // jobs의 값들을 works로 옮겨주는 작업
        works.insert({ jobs[i][0], jobs[i][1] });
    }

    while (works.size()) {
        // works에 원소가 있는 한 계속 반복
        
        multiset <pair<int, int>, cmp> now_working(works.begin(), works.end());
        multiset <pair<int, int>>::iterator iter = now_working.begin();
        // set은 값이 추가되거나 제거되었을 때 정렬이 실행되어 now_working으로 새로 만들어 추가한다.

        if (times < iter->first) times = iter->first;	
        // 최적의 값이 시간보다 클 때, 시간을 최적의 값까지 끌어온다.
        times += iter->second;
        // 작업을 실행시켜 종료시킨다.

        result += times - iter->first;	// 작업이 완료된 시간 - 작업이 신청된 시간

        now_working.erase(now_working.begin());	// 완료된 작업을 지운다.
        works.swap(now_working);	// 완료된 작업을 다시 works로 옮긴다.
    }

    return (int)(result / jobs.size());	// 평균 작업 시간 return
}

/*
정확성  테스트
    테스트 1 〉	통과 (4.89ms, 3.95MB)
    테스트 2 〉	통과 (3.93ms, 3.96MB)
    테스트 3 〉	통과 (3.08ms, 3.97MB)
    테스트 4 〉	통과 (2.93ms, 3.84MB)
    테스트 5 〉	통과 (4.59ms, 3.84MB)
    테스트 6 〉	통과 (0.03ms, 3.98MB)
    테스트 7 〉	통과 (2.53ms, 3.94MB)
    테스트 8 〉	통과 (1.61ms, 3.97MB)
    테스트 9 〉	통과 (0.32ms, 3.96MB)
    테스트 10 〉	통과 (5.41ms, 3.73MB)
    테스트 11 〉	통과 (0.01ms, 3.93MB)
    테스트 12 〉	통과 (0.02ms, 3.92MB)
    테스트 13 〉	통과 (0.01ms, 3.94MB)
    테스트 14 〉	통과 (0.01ms, 3.98MB)
    테스트 15 〉	통과 (0.02ms, 3.96MB)
    테스트 16 〉	통과 (0.01ms, 3.97MB)
    테스트 17 〉	통과 (0.01ms, 3.98MB)
    테스트 18 〉	통과 (0.02ms, 3.95MB)
    테스트 19 〉	통과 (0.01ms, 3.93MB)
    테스트 20 〉	통과 (0.01ms, 3.93MB)

채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
*/

시간 복잡도 : 2n

set의 자동 정렬 기능을 통하여 cmp를 설정해두고 최적의 값을 찾아
모든 값을 erase 할때까지 반복