[프로그래머스] 디스크 컨트롤러 - python[ Min Heap ]

[level 3] 디스크 컨트롤러 - 42627

문제 링크

성능 요약

메모리: 10.2 MB, 시간: 0.00 ms

구분

코딩테스트 연습 > 힙（Heap）

채점결과

Empty

문제 설명

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

예를들어

- 0ms 시점에 3ms가 소요되는 A작업 요청
- 1ms 시점에 9ms가 소요되는 B작업 요청
- 2ms 시점에 6ms가 소요되는 C작업 요청

와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다.

한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다.

- A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms)
- B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)
- C: 2ms부터 대기하다가, 12ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 16ms)

이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은 10ms(= (3 + 11 + 16) / 3)가 됩니다.

하지만 A → C → B 순서대로 처리하면

- A: 3ms 시점에 작업 완료(요청에서 종료까지 : 3ms)
- C: 2ms부터 대기하다가, 3ms 시점에 작업을 시작해서 9ms 시점에 작업 완료(요청에서 종료까지 : 7ms)
- B: 1ms부터 대기하다가, 9ms 시점에 작업을 시작해서 18ms 시점에 작업 완료(요청에서 종료까지 : 17ms)

이렇게 A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(= (3 + 7 + 17) / 3)가 됩니다.

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

제한 사항

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

입출력 예

jobs	return
[[0, 3], [1, 9], [2, 6]]	9

입출력 예 설명

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

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

문제가 잘 안풀린다면😢

힌트가 필요한가요? [코딩테스트 연습 힌트 모음집]으로 오세요! → 클릭

내가 푼 틀린 풀이

요청부터 종료까지 걸린 시간의 평균을 낮추려면 SJF(Shortest Job First)으로 접근해야 할 것으로 보인다.

1. jobs를 시작시간 기준으로 정렬한다.

2. 시간을 확인하여 현재 들어와 있는 작업 기준 가장 짧은 작업을 우선시하여 실행시킨다.

예외 : 현 시간에 들어온 작업이 없다면 가장 가까운 작업먼저 실행하는 조건이 있음

정렬을 어떻게 할까 고민하다가 그냥 sorted로는 안될거 같았음.

그래서 다른 사람의 풀이를 확인해보니 Min Heap을 쓰는 것을 볼 수 있었고, heapq 라이브러리를 사용하여 문제를 풀어봤으나 틀린 풀이.

import heapq
def solution(jobs):
    jobs = sorted(jobs, key = lambda x : x[0])
    time = jobs[0][0]
    N = len(jobs)
    heap = []
    answer = 0

    while jobs:
        removal = []
        for job in jobs:
            if job[0] <= time:
                removal.append(job)
                heapq.heappush(heap,[job[1],job[0]])
            else: break
        for val in removal:
            jobs.remove(val)
        if len(heap) > 0:
            job = heapq.heappop(heap)
            time += job[0]
            answer += (time - job[1])
        else:
            time =jobs[0][0]

    while heap:
        job = heapq.heappop(heap)
        answer += (job[0] + time - job[1])
        time += job[0]
    return answer/N

다른 사람의 풀이

나는 이미 heap에 넣은 값은 jobs에서 삭제하는 방식을 사용하였으나 이 사람은 start 라는 최소치를 설정하여 값들이 포함되지 않도록 걸러주는 방식을 사용하였다는 차이점이 있음.

또한 나는 heap에 아무 값도 없는 경우 job을 시작값 기준으로 초기에 정렬했기 때문에 가장 가까운 시작 값이 job의 첫번쨰 인덱스에 있을것이라 생각하여 time값을 job[0][0]으로 초기화해주는 방식을 사용했으나 아래 코드에서는 time +=1로 한 단계씩 나아가는 방식을 사용하였음.

내 코드에서 실패가 발생한 이유가 위 두가지 이유 중 하나이지 않을까 예상함.

import heapq

def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1 
    heap = []

    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])

        if len(heap) > 0: # 처리할 작업이 있는 경우
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
            i +=1
        else: # 처리할 작업이 없는 경우 다음 시간을 넘어감
            now += 1

    return answer // len(jobs)