[프로그래머스][힙] 디스크 컨트롤러 (211114)

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

이해도

★★☆☆☆

접근방법

• 처음에는 < 대기시간 = 작업시작시간(앞선 일이 끝난 시간) - 작업요청 시점> 이라 생각해서, 작업 소요 시간이 짧을수록 유리하다고 생각해 작업 소요 시간을 기준으로 정렬하였다. 
• 대기시간의 합을 최소로 만들도록 하고 (대기시간 + 총작업시간 // 3) 하면 되겠지..라고 순진한 생각을 했다.(레벨 3인지 몰랐지)
• 그런데 처음 시작하는 일은 작업요청 시점이 작은 일부터 시작하는 것이어서 거기서부터 꼬이기 시작했다...torr...결국 도움
• 크게 보면 처음엔 작업요청시간과 소요시간을 기준으로 정렬하고, 대기열과 작업열을 활용한다.
• 이후에는 소요시간이 적은 일부터 처리한다.
• 수행할 작업의 요청시점이 현재 작업 위치보다 앞인지 뒤인지에 따라 분기처리한다.
• 수행할 작업이 남아있는데 대기 리스트가 비어있으면 현재 미작동 중이므로 새로운 작업요청을 만날 때 까지 반복한다.

정렬방법 그리고 힙

• 특정 기준으로 리스트를  정렬하는 데는 두 가지 방법이 있다. itemgetter 와 람다 함수
• itemgetter 는 특정 인덱스를 기준으로 기준점을 여러개 잡아 정렬할 수 있다. (대박...)

• import operator jobs = [[0, 10], [3, 9], [3, 5]]
  jobs = sorted(jobs, key=operator.itemgetter(0, 1)) # 인덱스 0 , 1 기준 정렬
  #=> [[0, 10], [3, 5], [3, 9]]

• jobs = [[0, 10], [3, 9], [3, 5]]
  jobs.sort(key=lambda arr: arr[1]) # 인덱스 1을 기준으로 정렬
  
  #=> [[3, 5], [3, 9], [0, 10]]

itemgetter() 링크 파이썬 공식문서

• heappush 를 할 때, 인자를 2개 넣을 수 있다니!  그리고 앞 요소를 기준으로 힙푸시 된다니.. 신세계였다.

• waitings = []
  jobs = [[1, 9], [2, 6]]
  heappush(waitings, (jobs[0][1], jobs[0])) # jobs[0][1] 기준으로 힙푸시
  
  #=> waitings[(9, [1, 9])]
  #=> waitings[(6, [2, 6]), (9, [1, 9])]

 

코드코드

def solution(jobs):
    from heapq import heappush, heappop
    import operator

    current = 0
    answer = 0

    l = len(jobs)
    # 작업이 요청되는 시점을 기준으로 정렬한다.
    jobs = sorted(jobs, key=operator.itemgetter(0, 1))
    waitings = []
    heappush(waitings, (0, jobs.pop(0)))
    while waitings:

        processing = heappop(waitings)[1]

        # 요청 시점이 현재 시점보다 나중이라면(작업 미수행) 요청시점과 소요시간을 더한다.
        if processing[0] > current:
            current = processing[0] + processing[1]
        # 요청 시점이 현재 시점보다 먼저라면 현재 시점에 소요시간을 더한다.
        else:
            current += processing[1]

        # 작업의 요청부터 종료까지 걸린 시간을 정답에 더한다.
        answer += (current - processing[0])
        while True:
            # 수행할 작업이 남아있고 작업 요청시간이 작업위치보다 앞이라면
            if jobs and jobs[0][0] < current:
                # 소요시간이 적은 일부터 대기 리스트에 추가한다. => jobs[0][1] 기준으로 힙푸시
                heappush(waitings, (jobs[0][1], jobs[0]))
                # print(f'waitings{waitings}')
                jobs.pop(0)
            else:
                # 수행할 작업이 남아있고 대기 리스트가 비어있다면.. 먼저 요청 들어온 작업부터 처리한다.
                if jobs and len(waitings) == 0:

                    # 새로운 작업요청을 만날때 까지 돌린다.
                    prev = jobs[0][0]
                    while jobs:
                        job = jobs[0]

                        if job[0] != prev:
                            break

                        heappush(waitings, (job[1], job))
                        prev = job[0]
                        jobs.pop(0)

                break
    answer //= l

    return answer

print(solution([[0, 3], [1, 9], [2, 6]]))