[코딩테스트] 프로그래머스 - 디스크 컨트롤러 (Lv.3) in Python

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 작성.

 

더 자세한 설명 

-  programmers.co.kr/learn/courses/30/lessons/42627 

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

 

풀이

- 꽤 오랜 시간을 들였지만 두 개의 케이스를 통과하는 데 실패했다 ㅠ

- 결국 검색을 통해 해결했다. (velog.io/@younge/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC-%ED%9E%99 - 감사합니다! )

 

- 입력은 [작업 요청 시점, 작업 소요 시간]으로 주어진다.

- 현재 시간에서 처리 가능한 작업들은, 작업 요청 시점이 현재 시간 (currT)보다 작거나 같고, 이전 작업의 시작 시간 (prevJobStart)보다 큰 것들이다.

    - 처리 가능한 작업들은 따로 wait이라는 최소힙에 넣어준다.

    - 입력의 순서를 바꿔 [작업 소요 시간, 작업 요청 시점]으로 넣어주는데, 작업 소요 시간이 적은것부터 수행하는 것이 이득이기 때문.

 

- 만약 현재 시간에서 처리 가능한 작업들이 없는데, 작업은 남아있다면, 현재 시간을 하나 올려준다.

 

 

코드 구현

import heapq

def solution(jobs):
    lenJobs = len(jobs)
    currT, i, sumT = 0,0,0
    prevJobStart = -1
    wait = []
    
    while i < lenJobs:
    	for job in jobs:
            if prevJobStart < job[0] <= currT:
                heapq.heappush(wait,  [job[1], job[0]])
        if len(wait) > 0:
            curr = heapq.heappop(wait)
            prevJobStart = currT
            currT += curr[0]
            sumT = currT - curr[1]
            i += 1
        else:
            currT += 1
            
    return sumT // lenJobs

 

- while 문 안에 for 문에서, 이미 수행된 작업들또한 매 번 탐색되므로 효율성이 떨어진다. 하지만 jobs의 길이가 500이하로 작으니 괜찮은 걸로.

- 요 부분을 해결하려면 수행이 가능한 작업인 지 판명될 때마다 pop해줘야되는데, 리스트에서 pop하면 정렬에 다시 시간이 소요되므로 오히려 시간이 더 걸린다.

- jobs자체를 처음에 작업 요청 시간 - 작업 시간 순으로 정렬하면 더 나을 수도 있다!!