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

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

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

heap을 이용하는 문제라고 하는데 heap을 사용하지 않고 풀었습니다. 아무튼 풀이과정을 한번 적어보겠습니다.

 

우선 문제부터 요약하면, 

위의 그림처럼 task가 disk에 들어오게 되는데 이러면 disk는 이 task 들을 scheduling해야 합니다. 이때, 각 작업들의 요청부터 종료까지 걸린 시간의 평균의 최솟값을 return 해야 합니다.

 

즉 solution(jobs)에 

jobs : [작업이 요청되는 시점, 작업의 소요시간]을 담은 2d 배열

이 input으로 들어올 때, 각 작업들의 요청부터 종료까지 걸린 시간의 평균을 return 해야합니다. 

 

<Solution>

우선, 간단한 그림으로 아이디어를 확인해 봅시다. 

위 아이디어를 실제로 그대로 구현하면 문제가 풀립니다.

 

실제 구현은 아래와 같습니다.

(현재 available한 task중 길이가 짧은 task를 먼저 수행해야하므로 이 부분을 heapq등으로 구현해도 될 것 같습니다.)

def availble_jobs(left_jobs,current_time):
    # print(f'input : {left_jobs,current_time}')
    return_jobs = []
    for job in left_jobs:
        if job[0]<=current_time:
            return_jobs.append(job)
    # print(f'return_jobs : {return_jobs}')
    return return_jobs

def get_fast_ending_job(jobs): # get index of min job
    return min(jobs, key = lambda x : x[1])

def solution(jobs):
    total_len = len(jobs)
    total = 0
    time = 0
    left_jobs = jobs

    while(len(left_jobs) != 0):
        temp_job = availble_jobs(left_jobs,time)
        if len(temp_job) == 0:
            time+=1
            continue
        fast_ending_job = get_fast_ending_job(temp_job)

        total += (time-fast_ending_job[0]+fast_ending_job[1])
        time += fast_ending_job[1]
        left_jobs.remove(fast_ending_job)

    return total//total_len