(C#) 디스크 컨트롤러

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

프로그래머스

 

역대급 억까가 생긴 문제였다.

 

1. jobs를 요청 시간 순으로 정렬한다

2. 현재 시간(time)보다 요청 시간이 작거나 같은 작업을 힙에 추가한다.

3. 힙이 비어있지 않다면 다음 작업을 처리한다.

3-2. 힙이 비어있다면 다음 작업의 요청 시간까지 이동한다.

4. jobs의 모든 작업을 처리할 때까지 2 ~ 3-2 과정을 반복한다.

5. 이 과정에서 모든 작업이 요청되고 처리될때까지 시간 평균을 구한다.

 

문제 본문은 비교적 간단하지만 이를 위해 우선순위큐를 List 기반으로 직접 구현했다.

디버깅 용으로 ToString 함수와 Print 함수도 구현했다.

 

역대급 억까를 당했다는건 뭐냐면, 내 로컬 환경(VScode)에서 실행할 때는 멀쩡한 녀석이 테스트케이스만 돌리면 틀리는 것이었다.

예제의 [[1, 3], [1, 9], [2, 6]] 을 가지고 실행했을 때, heap에 [1, 9]가 두번 들어가는 문제가 있었다.

ChatGPT형님의 도움을 받아가며 온갖 의심되는 구현을 고쳐보았지만 하루를 꼬박 새도 해결되지 않았다.

끊임없는 질문과 탐색 끝에 원인을 찾았다.

 

원인은 테스트 환경인 Mono C# Compiler 6.10.0 에서의 버그 때문이었다.

지금은 Heap의 Add와 Remove과정에서 두 값을 교환할 때 고전적인 방식을 사용하지만, 처음 구현했을 때는 튜플을 이용한 교환 방식을 사용했었다.

// Tuple Swap
var a = 1;
var b = 2;
(a, b) = (b, a);

// result : a = 2, b = 1

그런데 이 방식의 교환에 버그가 있다는 것이다.

 

이 버그 때문에 heap에 Add나 Remove를 할 때 heapify가 제대로 작동하지 않았다.

 

이 방식을 고전적인 방식으로 바꾸니 해결되었다.

 

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[,] jobs)
    {
        int answer = 0;
        Heap<Job> heap = new Heap<Job>();

        // jobs를 요청 시간 순으로 정렬
        var jobList = new List<Job>();
        for (var i = 0; i < jobs.GetLength(0); i++)
        {
            jobList.Add(new Job(jobs[i, 1], jobs[i, 0], i));
        }
        jobList.Sort((x, y) => x.request.CompareTo(y.request));

        int time = 0;
        for (var i = 0; i < jobList.Count || heap.Count > 0;)
        {
            // 현재 시간(time)보다 요청 시간이 작거나 같은 작업을 힙에 추가
            while (i < jobList.Count && jobList[i].request <= time)
            {
                heap.Add(jobList[i]);
                i++;
            }
            // 힙이 비어있지 않으면 작업을 처리
            if (heap.Count == 0)
            {
                time = jobList[i].request;
            }
            else
            {
                var job = heap.Remove();
                time += job.time;
                answer += time - job.request;
            }
        }
        answer /= jobList.Count;
        return answer;
    }

    class Heap<T> where T : IComparable<T>
    {
        public List<T> heap = new List<T>();
        public int Count => heap.Count;

        public void Add(T value)
        {
            heap.Add(value);
            int i = heap.Count - 1;
            while (i > 0)
            {
                int parent = (i - 1) / 2;
                var t1 = heap[i];
                var t2 = heap[parent];
                if (t1.CompareTo(t2) < 0)
                {
                    T temp = heap[i];
                    heap[i] = heap[parent];
                    heap[parent] = temp;
                    i = parent;
                }
                else
                {
                    break;
                }
            }
        }

        public T Remove()
        {
            if (heap.Count == 0) throw new InvalidOperationException("Heap is empty");
            var result = heap[0];
            heap[0] = heap[heap.Count - 1];
            heap.RemoveAt(heap.Count - 1);
            int i = 0;
            while (true)
            {
                int left = i * 2 + 1;
                int right = i * 2 + 2;
                if (left >= heap.Count) break;
                int smallest = left;

                if (right < heap.Count && heap[right].CompareTo(heap[left]) < 0)
                {
                    smallest = right;
                }
                if (heap[i].CompareTo(heap[smallest]) <= 0) break;

                T temp = heap[i];
                heap[i] = heap[smallest];
                heap[smallest] = temp;

                i = smallest;
            }
            return result;
        }

        public void Print()
        {
            for (var i = 0; i < heap.Count; i++)
            {
                Console.WriteLine($"heap[{i}] : {heap[i].ToString()}");
            }
        }
    }

    struct Job : IComparable<Job>
    {
        public int time;
        public int request;
        public int index;
        public Job(int time, int request, int index)
        {
            this.time = time;
            this.request = request;
            this.index = index;
        }

        public int CompareTo(Job other)
        {
            int r = time.CompareTo(other.time);
            if (r != 0) return r;
            r = request.CompareTo(other.request);
            if (r != 0) return r;
            return index.CompareTo(other.index);
        }

        public override string ToString()
        {
            return $"job : ({index}, {request}, {time})";
        }
    }
}