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

jh Seo·2023년 7월 2일

우선순위 큐 프로그래머스 한번에 못 푼 문제

프로그래머스

목록 보기

15/32

개요

디스크 컨트롤러

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

예를들어

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 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

접근방법

개인적으론 매우 접근하기 어려웠던 문제다.
처음 생각한 방식은 재귀함수를 이용한 방식이였다.
첫 작업의 (시작시간부터 시작시간+소요시간) 시간 내에 존재하는 작업중에 (시작시간~ 시작시간+소요시간)이 제일 작은 작업을 찾고,
또 그 시간내부에 (시작시간~시작시간+소요시간)이 제일 작은 작업을 찾는 식으로 재귀를 짜야하나 싶어서 접근하다가 틀었다.
가만히 생각해보니 굳이 그런 방식으로 안 풀어도 될거 같았다.
그 다음 떠올린 방식은 처음에 모든 값의 (시작시간+소요시간)을 비교해서
제일 작은 값부터 처리한다.
각 작업이 끝났을 때의 총 시간을 curOffset변수에 저장하는 식으로 처리를 했다.
그 후, curOffset값보다 시작 시간이 작은 값들 중에 curOffset+소요시간 - 시작시간이 제일 작은 값부터 처리를 하고,
모든 시작 시간값이 curOffset보다 클 때는 요청 순서대로 처리를 하는 식이였다.
하지만 이런식으로 풀면 각 작업이 끝날때마다 현재 curOffset값 + 소요시간 - 시작시간 값을 남아있는 모든 대기작업들에 대해 연산 후, 제일 작은 값을 구해야 하므로 너무 낭비인것 같았다.
따라서 힌트를 좀 보니 굳이 시작시간~ curOFfset값을 상대로 정렬을 안하고 소요시간이 제일 작은 값들로만 그리디방식으로 풀어도 된다는 글을 봤다.
사실 소요시간으로만 기준을 잡아도 되는지 아리송해서,
몇가지 예시로 증명해봤다.
1. 소요시간이 더 긴값이 더 시작시간이 짧을 때
  예시로 [3,6], [5,4], [4,5] 이렇게 값이 들어오면
- [3,6]->[5,4] -> [4,5]
  sum(요청부터 처리시간까지)= 6-> 8 -> 14 = 6+8+14= 28
  curOffset(각 작업이 끝났을 때 시간)=9 -> 13 -> 18
- [3,6] -> [4,5] -> [5,4]
  sum= 6 -> 10 -> 13 = 6+10+13 = 29
  curOffset=9 -> 14 -> 18
  
  -> 소요시간이 더 짧은 값을 고르며 진행하는게 더 sum값이 적다
1. 소요시간이 더 긴값이 더 시작시간이 길 때
  예시로 [3,6], [6,5], [7,4] 이렇게 값이 들어오면
- [3,6] , [6,5], [7,4]
  sum(요청부터 처리시간 까지) = 6-> 8-> 11
  curOFfset=9-> 14-> 18
- [3,6], [7,4], [6,5]
  sum= 6-> 6-> 12
  curOffset= 9-> 13> 18
  
  ->소요시간이 더 짧은 값을 고르며 진행하는게 더 sum값이 작다.
1. 시작시간이 같을 때
  -> 이때는 무조건 소요시간 짧은걸 고르는게 맞다.
따라서 소요시간이 짧은 값들만 고르면서 진행해도 된다.
하지만 주의해야할 점은 하드웨어는 대기시간동안 가만히 있는게 아니라
먼저 온 요청부터 처리한다라는 점이다.
따라서 소요시간 작은값들 기준으로 차례대로 처리하면 안되고
시작시간을 잘 봐야한다.
각 작업이 끝난시간인 curOffset값보다 시작시간이 작은 값들만 실행할 수 있으며,
소요시간 제일 작은값이 curOFfset값보다 크다면 대기 작업중에 시작시간이 제일 작은 값을 실행해야한다.
처음 구현 과정은 복잡하게 구현했다.
우선순위 큐를 두개룰 사용해 하나는 시작시간 기준으로 정렬,
하나는 소요시간 기준으로 정렬했다.
처리한 작업들을 넣는 용도인 set을 하나 만들었다.
우선순위큐에서 작업을 꺼낼 때, set에 find연산으로 처리했는지 안 했는지 확인해서 pop연산을 하는 방식으로 작동했다.
하지만 구현하다 생각해보니 우선순위큐와 set을 합칠수 있는 자료구조가 있었다.
바로 map을 통해 key값을 정렬하며, value값으로 처리된건지 아닌지
bool형을 넣어줘서 저장하는 방식이다.
set과 동일하게 find도 O(logN)의 속도로 가능하므로 map을 이용해 구현했다.
따라서 최종적으로 자료구조를 두개 사용했다.
우선순위 큐와 map을 사용했는 데, 우선순위 큐는 key값을 시작시간으로 설정했다.
map은 key값으로 [소요시간, 시작시간]을 설정하고, value값은 bool형 변수로 둬서 처리한 작업인지, 처리못한 작업인지 설정했다.
처음에 우선순위큐에는 [시작시간, 소요시간] 순서로 값들을 저장한다.
map에는 key는 [소요시간,시작시간] 순서로, value는 처리안된 값들이므로 false값을 저장한다.

반복문은 우선순위 큐를 기준으로 돌린다.
우선순위큐의 top값을 map에서 조사해서 처리한 값이면 pop하고 처리되지 않은 값이 나올때까지 pop연산을 한다.

while (!diskWorkQueue.empty()) {
      bool didWork = false;
      //제일 먼저 요청한작업이 이미 완료된 작업이라면 pop연산
      if (timePriorityMap[{diskWorkQueue.top().second, diskWorkQueue.top().first}]) {
          diskWorkQueue.pop();
          continue;
      }

그 후 , map을 순회하면서 이미 처리한 값이면 continue한다.
현재 순회하는 값이 curOffset보다 시작시간이 큰 값이라면 continue한다.
조건에 맞는값이라면 didWork 변수를 true체크해준 후, curOFfset과
sum값 갱신해주고, 해당 변수를 처리했다는 뜻으로 value값을 true 처리해줬다.
처리해줬으므로 더 순회하지 못하게 break를 걸었다.

    for (auto iter = timePriorityMap.begin(); iter != timePriorityMap.end(); ++iter) {
          //이미 방문했다면
          if ((*iter).second) continue;
          //현재 curOffset보다 시작시간이 더 작은값이나올때까지 
          if ((*iter).first.second > curOffset) continue;

          didWork = true;
          curOffset += (*iter).first.first;
          sumOfRequestProcessTime += (curOffset - (*iter).first.second);
          (*iter).second = true;
          break;
      }

map순회가 끝났을 때, didwork변수가 false라면 조건에 맞는 값을 못 찾았다는 뜻이다.
이건 하드웨어가 대기중이라는 뜻으로 제일 먼저 요청된 값을 처리해야한다.
따라서 map이 아닌 우선순위 큐 diskWorkQueue에서 top값을 꺼내 처리하고 pop해준다.

//curOffset보다 작은 시작시간값이 없다면 하드가 쉬고있을 때다
	if (!didWork) {
		curOffset = diskWorkQueue.top().first +   diskWorkQueue.top().second;
        sumOfRequestProcessTime += diskWorkQueue.top().second;
        timePriorityMap[{diskWorkQueue.top().second,  diskWorkQueue.top().first}] = true;
        diskWorkQueue.pop();
      }

전체코드

#include <vector>
#include <queue>
#include <set>
#include <map>
#include<iostream>

using namespace std;


int solution(vector<vector<int>> jobs) {
    //답, 각 작업의 요청부터 종료까지 걸린 시간들의 합 , 각 작업이 끝났을때 총 시간,
    int answer = 0, sumOfRequestProcessTime = 0, curOffset = 0, jobsSize = jobs.size();


    //작업 들어온 목록 순서 first는 시작시간, second는 소요시간
    priority_queue<pair<int, int>,vector<pair<int,int>>,greater<pair<int,int>>> diskWorkQueue;
    //first는 소요시간, second는 시작시간, value는 완료되었는지 안되었는지
    map<pair<int, int>, bool> timePriorityMap;


    //시작은 무조건 처음 들어온 요청을 처리해야한다. -> 최소값으로 안해도됨

    //순서대로 하기위해서 큐에 푸시
    for (int i = 0; i < jobsSize; ++i) {
        diskWorkQueue.push({ jobs[i][0], jobs[i][1] });
        timePriorityMap[{jobs[i][1], jobs[i][0]}] = false;
    }
    curOffset = diskWorkQueue.top().first + diskWorkQueue.top().second;
    sumOfRequestProcessTime = diskWorkQueue.top().second;
    timePriorityMap[{diskWorkQueue.top().second, diskWorkQueue.top().first}] = true;
    
    //시작시간~curOffset+소요시간 값을 우선순위 큐를 이용해 제일 작은 값찾기 -> 소요시간이 제일 짧은거로 가면 된다
    while (!diskWorkQueue.empty()) {
        bool didWork = false;
        //제일 먼저 요청한작업이 이미 완료된 작업이라면 pop연산
        if (timePriorityMap[{diskWorkQueue.top().second, diskWorkQueue.top().first}]) {
            diskWorkQueue.pop();
            continue;
        }
        for (auto iter = timePriorityMap.begin(); iter != timePriorityMap.end(); ++iter) {
            //이미 방문했다면
            if ((*iter).second) continue;
            //현재 curOffset보다 시작시간이 더 작은값이나올때까지 
            if ((*iter).first.second > curOffset) continue;

            didWork = true;
            curOffset += (*iter).first.first;
            sumOfRequestProcessTime += (curOffset - (*iter).first.second);
            (*iter).second = true;
            break;
        }

        //curOffset보다 작은 시작시간값이 없다면 하드가 쉬고있을 때다
        if (!didWork) {

            curOffset = diskWorkQueue.top().first + diskWorkQueue.top().second;
            sumOfRequestProcessTime += diskWorkQueue.top().second;
            timePriorityMap[{diskWorkQueue.top().second, diskWorkQueue.top().first}] = true;
            

            diskWorkQueue.pop();
        }
    }

    return answer = sumOfRequestProcessTime / jobsSize;
}

문풀후생

되게 어려웠던 문제다.. 고민을 많이했고, 생각할 조건도 많아서 쉽게 풀지 못했던 문제다. 그나마 소요시간 기준으로 잡고 풀면된다는 힌트얻어서 쉽게 풀었지 아니면 더 복잡하게 풀었을 것같다.
매 작업끝날때마다 모든 처리된작업 순회하면서 처리시간-시작시간 업데이트하고 제일 작은값 불러오고 이런식으로

jh Seo

코딩 창고!

이전 포스트

[프로그래머스] 더 맵게

다음 포스트

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