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

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

 

이 문제는 우선순위 큐 ( 힙 ) 을 사용해서 푸는 문제였는데 몇가지 풀리지 않은 궁금증이 있다.

 

1.  실행 시간이 가장 작은걸 먼저 실행하는게 결과적으로 최소의 평균시간을 도출한다는 것을 어떻게 증명할 수 있는지?

2. heap 에 값을 push 할 때 실행시간은 같지만, 더 먼저 요청된 작업을 먼저 실행하든 말든 결과에는 영향이 없는데 이걸 어떻게 수학적으로 증명 할 수 있는지?

 

---> 수정

• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 라는 조건때문에 이 모든게 성립한다.
• 즉, 현재 수행 할 수 있는 작업들을 heap에 넣는데, 정렬 기준은 작업 시간의 오름차순으로 넣는다.

코딩테스트 연습 - 디스크 컨트롤러

import heapq;

def solution(jobs):
    jobs.sort(key=lambda x: (x[0], x[1]));
    i = 0;
    t = 0;
    ret = 0;
    beforeTime = -1;
    heap = [];

    while(i < len(jobs)):
        for job in jobs:
            if (beforeTime < job[0] <= t):
                heapq.heappush(heap, [job[1], job[0]]);
        
        if (heap) :
            beforeTime = t;    
            now = heapq.heappop(heap);
            t += now[0];
            ret += (t - now[1]);
            i += 1;
        else :
            t += 1;
    return ret // len(jobs)

https://codeforces.com/contest/1622/problem/C

Problem - C - Codeforces

import math
from collections import deque
t = int(input())
ret = [];
for _ in range(t):
    n, k = map(int,input().split());
    arr = list(map(int,input().split()));
    ans = 1e16;
    arr.sort();
    a1 = arr[0];
    p = [0] * (n+1);
 
    for i in range(n):
        p[i+1] = p[i] + arr[i];
 
    for i in range(n):
        x = math.ceil(a1 - ((k + a1 - p[n-i]) / (i+1)));
        if x < 0 :
            x = 0;
        ans = min(ans, x + i);
    
    ret.append(ans);
 
for a in ret:
    print(a);