Programmers - 디스크 컨트롤러

---

title: Programmers - 디스크 컨트롤러
date: 2022-10-04
tags:

• Algorithm

---

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

문제 요약

한 번에 하나의 작업만 수행 가능하며, 요청 시각과 소요 시간이 주어진다.
현재 수행중인 작업이 없다면 대기 시간 없이 즉각적으로 작업을 시작한다.
모든 작업이 완료되었을 때, 각 요청이 끝날 때까지 걸린 소요 시간들의 평균을 정수로 return한다.

문제 풀이

이 문제의 핵심은 요청 이후 리소스를 할당받지 못하여 대기하는 작업의 시간을 줄이는 것이다.
요청한 작업이 종료될 때까지 시간을 측정하기에, 각 작업의 소요 시간은 기본적으로 누적이 된다.
그렇기에 자신이 할당받을 때까지 대기하는 시간을 최대한 줄여야 한다.
이를 위해서는 동일한 시간 안에 더 많은 개수의 작업이 끝나야 한다.
결국 리소스 할당이 가능할 때, 작업의 소요 시간이 가장 짧은 것을 할당해주면 된다.


요청한 작업들을 시간 순서대로 정렬한다.
이를 각 시각에 맞추어 priority_queue에 저장하면 priority_queue에는 아직 끝나지 않은 작업 중 소요 시간이 가장 짧은 것이 제일 위에 존재한다.
priority_queue에 작업 추가 - 작업 할당을 반복하면 총 소요 시간을 구할 수 있다.


이는 OS의 SJF Scheduler의 방식과 동일하다.
이 문제에 조건을 추가할수록 Scheduler의 발전을 따라갈 가능성이 높다.

프로그램

#include <vector>
#include <algorithm>
#include <queue>

using std :: vector ;
using std :: priority_queue ;

struct jobInfo
{
    int iRequestTime ;
    int iUsedTime ;
} ;

struct comp
{
    bool operator () ( jobInfo & first , jobInfo & second )
    {
        return first.iUsedTime > second.iUsedTime ;
    }
} ;

int solution ( vector < vector < int > > jobs )
{
    int answer = 0 ;
    std :: sort ( jobs.begin () , jobs.end () ) ;
    priority_queue < jobInfo , vector < jobInfo > , comp > pqJobs ;
    int iJobIndex = 0 ;
    int iJobSize = jobs.size () ;
    int iTime = 0 ;



    for ( int i = 0 ; i < iJobSize ; ++i )
    {
        for ( ; iJobIndex < iJobSize ; ++ iJobIndex )
        {
            if ( iTime < jobs [ iJobIndex ] [ 0 ] )
                break ;

            pqJobs.push ( { jobs [ iJobIndex ] [ 0 ] , jobs [ iJobIndex ] [ 1 ] } ) ;
        }

        if ( pqJobs.empty () )
        {
            iTime = jobs [ iJobIndex ] [ 0 ] ;
            -- i ;
        }
        else
        {
            jobInfo currentJob = pqJobs.top () ;
            pqJobs.pop () ;
            iTime += currentJob.iUsedTime ;
            answer += iTime - currentJob.iRequestTime ;
        }
    }


    return answer / iJobSize ;
}