[C++]디스크 컨트롤러

요약

• vector 정렬
• Priority Queue 적용 및 구조체 내부 연산자 오버로딩을 통한 정렬
• 컨트롤러 내부 로직

풀이과정

우선 예제에서 나왔듯이, 평균 대기시간이 가장 짧은 스케줄러는 최단작업 우선 스케줄링(Shortest Job Controller)이다.

평균 대기시간을 최소화하는데에 중점을 두었으나, 지속적으로 양보하는 상태인 '기아 상태'가 발생할 수 있다.

아무튼.. 요구 조건에 따라 SJF를 구현하는 문제이다.

1. Vector 정렬

일단, input으로 주어지는 jobs가 들어온 시간순으로 정렬되어있으리란 보장이 없었다.

그리고 들어온 시간이 같은 경우, 소요 시간이 짧은 순으로도 초기 정렬을 해주었다.

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

    sort(jobs.begin(),jobs.end(),cmp);  //jobs 입력시간 순 정렬

2. Priority Queue & Struct Operator Overloading

쓰려는 이유

이 문제는 작업이 push되고 pop 되는 구조 ==> Queue

스케줄러에 들어온 작업들은 작업시간이 짧은 순으로 정렬되어야 한다. ==> Priority Queue

우선순위 큐의 커스텀 정렬을 위해서는 struct operator overloading이 필요하다.

따라서 아래와 같이 struct를 선언하였다.

struct Job
{
    int input_t;    //요청이 들어오는 시간
    int need_t;     //소요 시간
    Job(int a, int b)
    {
        input_t = a;
        need_t = b;
    }
    Job(vector<int> a)
    {
        input_t = a[0];
        need_t = a[1];
    }
    
    bool operator<(const Job& other) const
    {   // need_t 내림차순으로 연산자 오버로딩
        return need_t > other.need_t;
    }
};


priority_queue<Job> sjf;    //소요 시간 오름차순 pq 선언

3. 컨트롤러 내부 로직

전체 작업은 반복문으로 진행되며, jobs에 있는 모든 요소에 대해 진행한다.

count라는 값을 통해

또한 시간 파악을 위해 cur_time 이라는 변수도 선언하였다.

int count = 0;      //prority queue에 들어간 작업의 수
int cur_time = 0;   //작업 완료 기준 현재 시간

    for(int i = 1; i <= jobs.size(); i++)
    {
		...
    }

1. 작업 push 해주기

그냥 jobs[count] 값을 큐에 push해준다.

주의할 것은 sjf가 비어있는 경우 예외 처리를 해줘야 함.

        if(sjf.empty()) //스케줄러가 비었다면, 먼저 요청이 들어온 작업 push
            sjf.push(jobs[count++]);
        Job cur = sjf.top();
        sjf.pop();

2. 시간 처리

cur_time을 업데이트 해주고, cur_time 기반으로 해당 작업의 대기 시간을 answer에 더해준다.

역시 cur_time 설정에 여러 조건을 고려해서 설정해줘야 한다.

        cur_time = max(cur_time,cur.input_t) + cur.need_t;
        answer += cur_time - cur.input_t;

cur_time의 경우 현재 시간과 작업 요청이 들어온 시간 중 max 값을 기반으로 잡고, 작업 시간을 더한다.

대기 시간은 cur_time(작업 완료 시점) - 현재 작업이 들어왔던 시간을 빼면 된다.

3. 스케줄러 push 하기

여기서 count가 쓰이게 된다. 들어가지 않은 작업들 중, cur_time보다 input_time이 작거나 같은 녀석들을 모두 sjf에 push해준다.

        while(count < jobs.size())
        {
            if(jobs[count][0] <= cur_time)
                sjf.push(jobs[count++]);  
            else
                break; 
        }

이미 input_t 기준으로 오름차순 정렬을 하였기 때문에, if문을 통과하지 못하면 이후 값들도 통과할 수가 없다. 따라서 break한다.

 

이후 answer는 대기 시간의 합이기 때문에 jobs.size()로 나눠주면 끝난다.

코드

#include <bits/stdc++.h>
using namespace std;

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

struct Job
{
    int input_t;    //요청이 들어오는 시간
    int need_t;     //소요 시간
    Job(int a, int b)
    {
        input_t = a;
        need_t = b;
    }
    Job(vector<int> a)
    {
        input_t = a[0];
        need_t = a[1];
    }
    
    bool operator<(const Job& other) const
    {   // need_t 내림차순으로 연산자 오버로딩
        return need_t > other.need_t;
    }
};



int solution(vector<vector<int>> jobs) {
    int answer = 0;
    sort(jobs.begin(),jobs.end(),cmp);  //jobs 입력시간 순 정렬
    priority_queue<Job> sjf;    //소요 시간 오름차순 pq 선언
    int count = 0;      //prority queue에 들어간 작업의 수
    int cur_time = 0;   //작업 완료 기준 현재 시간
    
    for(int i = 1; i <= jobs.size(); i++)
    {
        // cout << "작업 " << i << " : ";
        if(sjf.empty()) //스케줄러가 비었다면, 먼저 요청이 들어온 작업 push
            sjf.push(jobs[count++]);
        Job cur = sjf.top();
        sjf.pop();
        // cout << cur.input_t << "," << cur.need_t << endl;
        cur_time = max(cur_time,cur.input_t) + cur.need_t;
        answer += cur_time - cur.input_t;
        // cout << "소요시간 : " << cur_time << "-" << cur.input_t << "=" << cur_time-cur.input_t << endl;
        while(count < jobs.size())
        {
            if(jobs[count][0] <= cur_time)
                sjf.push(jobs[count++]);  
            else
                break; 
        }
    }
    
    return answer/jobs.size();
}

테스트케이스

이 문제는 최초 구현이 다소 쉬운 것에 반해, 섬세하게 예외처리같은걸 해줘야 하는 문제라 느꼈다.

그만큼 테스트케이스가 정말 절실한 문제라서 ㅋㅋㅋㅋㅋㅋ 질문하기에 있던 TC 중 도움되었던 테케를 정리해봤다.

 

[[24, 10], [28, 39], [43, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]]

72

 

[[1, 9], [1, 4], [1, 5], [1, 7], [1, 3]]

13

 

[[10, 10], [30, 10], [50, 2], [51, 2]]

6

 

[[0, 10], [4, 10], [15, 2], [5, 11]]

15

 

[[0, 3], [1, 9], [2, 6], [30, 3]]

7

 

[[1000, 1000]]

1000

 

[[0, 10], [2, 12], [9, 19], [15, 17]]

25

 

[[0, 10], [2, 10], [9, 10], [15, 2]]

14

 

[[0, 3], [1, 9], [2, 6]]

9

 

기억할 점

• Priority Queue와 Struct Operator Overloading을 통한 커스텀 정렬
  • 구조체 내부 연산자 오버로딩이 직관적으로 느껴지지도 않고, sort의 커스텀 함수와 반대로 return이 되어서 많이 헷갈린다.