프로그래머스 디스크 컨트롤러 (Python)

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

프로그래머스

---

문제 해결을 위한 과정

이 문제의 경우 heapq를 이용하면 해결할 수 있는 문제였습니다.

과정을 설명하면 다음과 같습니다.

 

1. jobs 리스트 정렬

2. 맨 처음 인덱스에 해당하는 값을 이용해 finish, answer 할당(finish는 작업이 끝나는 시간, answer는 대기 시간)

3. 다시 jobs 리스트를 정렬하며 finish 보다 request가 이전인 경우(작업 중에 들어온 요청인 경우) heapq에 삽입

4. heapq가 존재하면 가장 짧은 duration을 가진 작업을 이용해서 finish, answer 재할당

5. heapq가 존재하지 않으면 jobs리스트를 정렬하며 맨 처음 인덱스에 해당하는 값을 이용해 finish, answer 할당

 

이 부분에서 8번 18번 테스트 케이스를 틀렸었는데 이는 동일 request에 여러 작업이 들어올 수 있기 때문입니다. 따라서 jobs 리스트를 정렬 시 lambda를 이용해서 request기준으로 오름차순을 하고, 만약 request가 같다면 duration으로도 오름차순 정렬을 해주면 됩니다.

---

소스코드

import heapq

def solution(jobs):
    answer = 0
    length = len(jobs)
    length2 = len(jobs)
    jobs.sort(key = lambda x: (x[0], x[1]))
    finish = 0
    finish = jobs[0][1] + jobs[0][0]
    answer += jobs[0][1]
    jobs.pop(0)
    length2 -= 1
    
    while length2 != 0:
        jobs.sort(key = lambda x: (x[0], x[1])) 
        q = []
        for i in range(len(jobs)):
            request, time = jobs[i]
            if request <= finish:
                heapq.heappush(q, (time, request, i))
        if len(q) != 0:
            time, request, idx = heapq.heappop(q)
            if request <= finish: # 하드디스크 작업 수행 중 들어온 요청인 경우
                finish = finish + time
                answer += finish - request
                length2 -= 1
                jobs.pop(idx)
            else:
                heapq.heappush(q, (time, request, idx)) # 하드디스크가 작업 수행을 하지 않는 경우   
        else:
            jobs.sort(key = lambda x: (x[0], x[1])) 
            request, time = jobs[0] # 가장 앞에 작업 수행
            finish = request + time
            answer += finish - request
            jobs.pop(0)
            length2 -= 1
    answer = answer // length
    
    return answer