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

 문제

 

 

 문제 상황

 

- 프로세스에 작업 우선순위를 정하는 문제다. 단순히 들어온 순서대로 작업이 진행되는 것이 아니라 작업이 대기열에 올라온 후 완료될 때까지 시간의 합 평균이 가장 작게 작업을 하는 순서를 정하는 문제이다. 소수점 이하는 버리고 그 평균 시간을 출력한다.

 

 

 

 해결 전략

 

- 최소, 혹은 최대의 요소를 선택할 때 heap 자료구조를 사용한다.

 

 

 

 코드

 

import heapq
def solution(jobs):
    heapq.heapify(jobs)
    # 작업의 수
    cnt = len(jobs)
    # 시간을 나타내는 변수
    sec = 0
    # 결과를 담을 변수
    result = []
    while cnt > 0:
        # 후보군에서 제외될 때에 담겨질 변수
        temp = []
        # 현재 시간 이전에 들어온 작업들을 모은다
        for i in range(len(jobs)):
            x = heapq.heappop(jobs)
            # 이미 대기열에 있는 작업이면 temp에 넣는다
            if x[0] <= sec:
                temp.append(x)
                continue
            # 현재 시간 이후 작업이라면 아직 대기열에 없으므로 다시 넣어주고 끝낸다.
            else :
                # 이 작업을 하지않아 오류가 발생했다. 아직 대기열에 오지 않은 작업이므로 그냥 
                # break를 하면 작업 자체가 사라져버린다.
                heapq.heappush(jobs,x)
                break
        # 여기서 오류가 발생했다.
        # 반드시 작업들이 연결되어 있는 것이 아니기 때문에 현재 시간 기준으로 작업이 비어있을 수 있다.
        # 그런 경우 시간만 올려주어야한다.
        if len(temp) == 0:
            sec += 1
            continue
        # 작업들이 존재할 경우 완료 시간이 빠른 작업을 우선 꺼낸다.
        temp.sort(key = lambda x : x[1], reverse=True)
        t = temp.pop()
        # 작업 시간만큼 시간을 점프
        sec += t[1]
        # 대기시간을 계산하기 위해 작업 완료된 시점에서 프로세스에 올라온 시간을 뺀다.
        result.append(sec-t[0])
        # 작업의 개수를 한개 줄인다.
        cnt -= 1
        # 진행되지 않은 작업을 다시 heap에 넣는다.
        for i in range(len(temp)):
            heapq.heappush(jobs, temp[i])
    return sum(result)//len(result)

 

 

 해설

 

- 코드에 해설 첨언

 

 

 

 새로 학습한 것 & 실수 

 

- 너무 예시로 나온 케이스를 위주로 생각하다보니 다른 케이스를 생각하지 못했다. 문제의 조건을 보면서 예시에 나오지 않은 상황을 생각할 필요가 있다.

 

- 좀 더 생각을 정제하고 시뮬레이션 해본 뒤 프로그래밍을 시작하는게 더 좋을 것 같다.

 

 

 

 

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