Programmers_Heap_디스크 컨트롤러

[힙(Heap)] 디스크 컨트롤러

문제

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

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

입출력 예

jobs return

[[0, 3], [1, 9], [2, 6]] 9

접근 방법

1. 하드 디스크 jobs의 일들을 처리할 리스트 inProcess에 순차적으로 넣는다. 이유는 하드리스크가 작업을 수행하고 있지 않을때에는 먼저 요청이 들어온 작업부터 처리해야한다는 조건 때문이다.
2. inProcess 리스트에 작업을 요청할때(push 할때) 기존 jobs에 있는 순서[요청시간,처리시간]와 반대되도록 하는것이 중요하다. 즉, [처리시간,요청시간] 순으로 push를 하면 일처리를 할때 처리시간이 짧은 순서대로 진행 할 수 있기 때문이다.
3. 현재 일을 처리 중인지, 아닌지를 판단할 수 있는 bool 'working'을 만든다.
4. 현재 일처리중이아니라면, inProcess에 처리 가능한 일들중 일처리시간이 가장 짧은 것부터 시작하면 된다.
5. 모든일을 처리하면 while루프에서 나온다.

Code | Python

import heapq
def solution(jobs):
    sec = -1
    answer = 0
    heapq.heapify(jobs)
    inProcess = []
    l = len(jobs)
    working = False

    while True:        
        #loop out 
        if not jobs and not inProcess and not working : break
        sec += 1

        # at some point(sec), push over to heap list from jobs
        while jobs:
            if jobs[0][0] == sec:
                heapq.heappush(inProcess,[jobs[0][1],jobs[0][0]])
                heapq.heappop(jobs)
            else: break
            if not jobs: break
		
        #check if the machine is working or not
        if not working: #if not, then start working
            if not inProcess: continue
            p_cnt = inProcess[0][0] - 1
            p_start = inProcess[0][1] -1
            heapq.heappop(inProcess)
            working = True
        else: p_cnt -= 1 #if working, then keep working
            
        #check if working is done. if yes, +answer then, make 'working' back to False
        if p_cnt == 0:
            answer += sec - p_start
            working = False

    return answer//l

ScreenShot & Output

#1 Input: solution([[0, 3], [10, 3], [2, 4]])
#1 Output: 3

#2 Input: solution([[0, 1], [1, 1], [3, 1], [2,6],[50, 7]])
#2 Output: 4

2회차 답안

import heapq
def solution(jobs):
    answer, ms = 0, -1
    length = len(jobs)
    working = False
    requested = []
    heapq.heapify(jobs)
    end = -1

    while True:
        if not jobs and not requested and not working: break
        ms += 1

        #각 해당 시간에 할당 가능 job을 requested에 할당(heappush)
        while jobs:
            if jobs[0][0] == ms:
                heapq.heappush(requested,[jobs[0][1],jobs[0][0]])
                heapq.heappop(jobs)
            else: break
        
        #일하고 있는 중인지, 일이 완료되는 시점인지 확인
        if working and ms == end:
            working = False
        
        #일하지 않는 중이면, 일 할당
        if not working:
            if not requested: continue
            temp = heapq.heappop(requested)
            end = ms + temp[0]
            start = temp[1]
            answer += end - start
            working = True
            
        
    return answer//length
print(solution([[0, 3], [1, 9], [2, 6]]))