힙_디스크 컨트롤러_Python

문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

문제에 주어진 예와 같습니다.

• 0ms 시점에 3ms 걸리는 작업 요청이 들어옵니다.
• 1ms 시점에 9ms 걸리는 작업 요청이 들어옵니다.
• 2ms 시점에 6ms 걸리는 작업 요청이 들어옵니다.

 

---

접근 방법

1. heapq를 바로 적용할 생각이 나지 않아 정렬과 리스트로 먼저 접근

딱 기본 테스트 케이스와 20번을 제외한 모든 테스트에서 실패한다.

무언가 조건을 빼먹은 모양이다.

여기서 소요시간을 오름차순 정렬하는 이유는 그리디 알고리즘을 생각하는 것처럼 평균 최단 시간을 구하기 위해선 소요시간이 작은것부터 계산해야 하기 때문이다.

import heapq

def solution(jobs):
    answer = 0
    heapq.heapify(jobs)
    # 소요 시간 오름차순 정렬
    sorted_list = sorted(jobs, key=lambda x:x[1])
    # 리스트가 되어 heappop() 등 heapq 메소드 사용불가능
    # print(sorted_list)
    # [[0, 3], [2, 6], [1, 9]]
    start = 0
    
    for i in range(len(sorted_list)):
        if sorted_list[i][0] <= start:
            start += sorted_list[i][1]
            answer += start - sorted_list[i][0]
            
    
    return answer // len(jobs)

 

---

개선

질문하기의 테스트 케이스 들을 추가하여 원인을 찾았다.

두 가지 테스트 케이스를 보았을때 처음 작업 투입 시점이 1인 경우를 고려하지 않았었다.

즉, 정렬을 한 후 반복문을 모두 돌아도 start 초기 값 0보다 작거나 같은 값이 나오지 않았다.

아래 모두 반복한 후에도 start 값을 갱신하지 않는 경우를 고려한 조건을 추가하였다.

if i == len(sorted_list) - 1:
	start += 1

---

그래도 개선되지 않았다.

반복문을 모두 돌아도 start 값이 갱신되지 않는다면 1을 더하고 다시 한번 반복문을 돌려야하기에

while문을 사용해 내부 for문으로 사용하기로 했다.

작업이 반영(완료)된 인덱스는 지워준다.(종료 조건을 리스트가 존재하면으로 했기때문)

여기서 break 로 for문을 종료 시켜주고 다시 while을 이용해 반복해주는 조건으로 사용해줘야한다.

그렇지 않으면 IndexError가 발생한다.(Out of range)

def solution(jobs):
    answer = 0
    # 소요 시간 오름차순 정렬
    sorted_list = sorted(jobs, key=lambda x:x[1])
    # 리스트가 되어 heappop() 등 heapq 메소드 사용불가능
    # print(sorted_list)
    # [[3, 3], [10, 3], [1, 10]]
    
    start = 0
    while sorted_list:
        for i in range(len(sorted_list)):
            # 작업 시점이 start보다 크면 pass
            if sorted_list[i][0] <= start:
                start += sorted_list[i][1]
                answer += start - sorted_list[i][0]
                sorted_list.pop(i)
                break
            # 반복문을 모두 돌았을 경우에도!
            # 작업 시점 0초에 투입되는 시간이 없다면 start를 1 증가시켜줘야함
            if i == len(sorted_list) - 1:
                start += 1
            
    
    return answer // len(jobs)

---

2. heaqp 사용한 우선순위 큐 풀이

우선순위 큐 해설은 다른 블로그를 참고하고 이해하는 수준이었다.

레벨3부터는 난이도가 확올라가는걸까 생각조차 못했던 방법이다.

나에게는 차라리 정렬을 이용해 푸는게 나은 방법이다.

출처 : [프로그래머스] 디스크 컨트롤러(Python, Java) (tistory.com)

[프로그래머스] 디스크 컨트롤러(Python, Java)

import heapq

def solution(jobs):
    answer = 0
    min_heap = []
    # 지난 시각
    last = -1
    # 현재 시각
    now = 0
    # 처리한 작업의 개수
    count = 0
    length = len(jobs)
    
    # count가 jobs의 개수가 될때까지 반복
    while count < length:
        for job in jobs:
            #job이 last와 now 사이면, answer에 (now - job이 들어온 시간) 더하고, 힙에 job 소요시간 삽입
            if last < job[0] <= now:
                answer += (now - job[0])
                heapq.heappush(min_heap, job[1])
        
        # heap이 비어있지 않다면
        if min_heap:
            # answer에 (힙 길이 * 힙 최소값)을 더한다.(힙에 들어있는 job들이 모두 힙 최소값만큼 기다려야 하므로)
            answer += (len(min_heap) * min_heap[0])
            #  last를 now로, now에는 힙 최소값을 더한다.
            last = now
            now += heapq.heappop(min_heap)
            # job 하나를 처리했으니 count를 1 더한다.
            count += 1
        # 힙이 비어있으면 now를 1 더한다.
        else:
            now += 1
            
    return answer // length
    

---

시간복잡도

1.heapq를 바로 적용할 생각이 나지 않아 정렬과 리스트로 먼저 접근

정렬 => O(N logN)

while => N만큼 반복 * N만큼 반복 => O(N^2)

총 시간복잡도는 O(N^2).

2. heaqp 사용한 우선순위 큐 풀이

while => 결국 Jobs의 요소 갯수만큼 반복하므로 O(N^2)

총 시간복잡도는 O(N^2)으로 예상된다.

 

출처 :  [프로그래머스] 디스크 컨트롤러(Python, Java) (tistory.com)

[프로그래머스] 디스크 컨트롤러(Python, Java)