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

Jeuk Oh·2021년 9월 7일

programmers python

코딩문제풀이

목록 보기

12/14

문제

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

풀이

아이디어

어음... 일단 task가 비어있을 때는 가장 가까운 요청을 작업하고,

작업 중에 요청이 쌓였을 때 뭐부터 처리하냐를 결정하는 것이 관건

1개만 쌓여있는데 그 친구가 너무 긴 친구면 기다려줘야하나?

예를 들어 이런 경우에도 D를 먼저 처리하는 것이 맞는가?

A랑 D만 있다고 생각하면 기다렸다가 A를 처리하면 총 요청 ~ 종료 시간은 3+200+4 = 207
먼저 들어온 D부터 처리하면 총 시간은 3+200+202 = 405

그런데 다행히 조건에서 task가 비어있으면 가까운 요청부터 작업한다하니 여기까진 고려안하고 405를 선택해도 된다.

그럼 작업이 2개이상 쌓여있을 때 무엇을 먼저 처리하냐가 되는데 이건 처리 시간이 가장 짧은 친구부터 처리해야한다.

(너무 날먹 그림판인가 ㅎㅎ;;)

암튼 예제에서 두 경우에서 차이가 나는 이유는 후순위로 밀린 친구가 앞 순위 애들의 작업시간만큼 기다려주기 때문이다. 당연히 앞순위 작업시간이 짧은 것이 후순위가 덜 기다리므로 더 좋다. 처리시간이 짧은 친구들부터 처리하면 되겠다.

구현적 아이디어

먼저 시간을 0으로 놓고 작업을 쌓는 task라는 빈 배열 만든다.

주어진 작업들인 jobs가 끝날 때까지 (모든 작업을 할 때 까지)

task가 비어있다면 jobs에서 가장 가까운 작업을 빼내서 처리한다.

모든 작업은 처리가 끝나면 시간을 지나게 하고, jobs에서 요청 시간이 현재 시간보다 빠른 친구들을 task에 heappush로 쌓아둔다. (작업 시간이 작은 것이 우선으로 나오도록)

task가 있다면 task에서 heappop으로 빼서 처리와 task에 새로운 작업들을 heappush하는 것을 반복. task가 비거나 jobs가 끝날 때까지 반복한다.

작업이 끝나면 answer에 (작업이 끝난 시간 - 요청된 시간) 을 더해주어 답을 계산한다.

task가 비면 다시 1번으로 가서 반복.
jobs가 먼저 끝나면 task가 남아있으니 남은 task를 끝내는 작업을 반복.

코드가 조금 반복성이 있지만, 이렇게 하닌까 pass가 나왔다.

구현


from heapq import heapify, heappush, heappop

def solution(jobs):
    anw = 0
    task = []
    L = len(jobs)
    jobs.sort(reverse=True)
    t = 0
    while jobs:
    	# 작업 하나 하기
        # task가 비었으면 jobs 직송
        if not task:
            now_task = jobs.pop()
            if t >= now_task[0]:
                t += now_task[1]
            else:
                t = now_task[0]+now_task[1]
            anw += now_task[1]
        # task가 있으면 거기서 뽑아서 하기
        else:
            now_task = heappop(task)
            t += now_task[0]
            anw += t-now_task[1]
            
        # 여기까지가 작업 하나 마무리   
        # 지난 시간만큼 밀린 작업 task에 넣기
        # heap때문에 원본과 반대로 넣음 -> 이거 때문에 코드가 애매한 반복성이 좀..
        cur = len(jobs)-1
        while cur >= 0 and jobs[cur][0] < t:
            o_task=jobs.pop()
            heappush(task, (o_task[1],o_task[0]))
            cur -= 1
            
    # jobs는 끝났는데 task가 남았으면 마무리
    while task:          
        now_task = heappop(task)
        t += now_task[0]
        anw += t-now_task[1]
    
    
    return int(anw/L)