<Lv.3> 디스크 컨트롤러 (프로그래머스 : C#)

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

📕 문제 설명

한 번에 하나의 작업만 처리할 수 있는 디스크가 있다. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리했을 때 평균 시간 반환하기

• Input
  [작업 요청되는 시점, 작업 소요시간]
• Output
  요청~종료까지 가장 작게 걸리는 평균 시간

예제

풀이

우선 순위 큐 활용한 풀이
1. jobs를 시작 순서로 정렬한 다중 배열 생성
2. 최소 힙을 만들고 거기에 시작 시간 기준 만족되는 job들을 넣는다. 여기서 최소 힙의 기준은 소요 시간이다.
3. 최소 힙에서 뺀 값을 기준으로 현재 시간을 갱신해주고 위의 작업들을 반복한다.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(int[,] jobs) {
        int answer = 0;
        int[][] jobArray = new int[jobs.GetLength(0)][];
        
        for (int i = 0; i < jobs.GetLength(0); i++)
        {
            jobArray[i] = new int[2] {jobs[i, 0], jobs[i, 1]};
        }
        
        jobArray = jobArray.OrderBy(y => y[0]).ToArray();
        
        PriorityQueue pq = new PriorityQueue();
        
        int finishedCount = 0;
        int currTime = 0;
        int index = 0;
        
        while (finishedCount < jobArray.Length)
        {
            while(index < jobArray.Length && jobArray[index][0] <= currTime)
            {
                pq.Enqueue(jobArray[index][0], jobArray[index][1]);
                index += 1;
            }
            
            if(pq.IsEmpty())
            {
                currTime = jobArray[index][0];
            } 
            else
            {
                var job = pq.Dequeue();
                answer += currTime + job.Item2 - job.Item1; // 걸린 시간 = 현재 시간 + 소요 시간 - 요청 시간
                currTime += job.Item2;
                finishedCount++;
            }
        }
        
        return (int) Math.Truncate((double) (answer / jobArray.Length));
    }
}

public class PriorityQueue
{
    List<(int startTime, int workTime)> _heap = new List<(int startTime, int workTime)>();
    
    public void Enqueue(int startTime, int workTime)
    {
        _heap.Add((startTime, workTime));
        
        int now = _heap.Count - 1;
        while(now > 0)
        {
            int next = (now-1)/2; // 부모 
            if(_heap[now].workTime >= _heap[next].workTime) break;
            // 들어온 데이터 <= 부모 -> swap
            var temp = _heap[now];
            _heap[now] = _heap[next];
            _heap[next] = temp;
            
            now = next; // 검사 위치 이동
        }
    }
    public (int, int) Dequeue()
    {
        var ret = _heap[0];
        
        // 마지막 데이터 루트로 이동
        int lastIndex = _heap.Count - 1;
        _heap[0] = _heap[lastIndex];
        _heap.RemoveAt(lastIndex);
        lastIndex--;
        
        int now = 0; // 현재
        while(true)
        {
            int left = 2 * now + 1;
            int right= 2 * now + 2;
            
            int next = now; 
            if(left <= lastIndex && _heap[next].workTime >= _heap[left].workTime) next = left;
            if(right <= lastIndex && _heap[next].workTime >= _heap[right].workTime) next = right;
            if(next == now) break;
            
            var temp = _heap[now];
            _heap[now] = _heap[next];
            _heap[next] = temp;
            
            now = next;
        }
        return ret;
    }
    
    public bool IsEmpty()
    {
        return _heap.Count == 0;
    }
}

결과