프로그래머스 - 디스크 컨트롤러(힙(heap))

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

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

# 문제 설명

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

예를 들어 요청이 들어오고 이를 처리하는 방법은 다음과 같다.

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

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

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

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

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

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

각 작업의 요청부터 종료까지 걸린 시간의 평균은 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

 

# 풀이

- 작업 소요시간 별로 jobs를 정렬하고, 현재 시간(i)에 대해 작업 요청시간이 작거나 같으면 해당 작업을 수행한다.

- 수행하면서 대기한 시간(wait)과 소요시간을 누적합하여 총 소요시간(result)을 구한다.

- 총 소요시간(result)을 작업 수(length)로 나눠서 평균 작업 소요시간을 출력한다.

def solution(jobs):
    jobs.sort(key=lambda x: x[1])
    length = len(jobs)
    
    wait, i, cnt, result = 0, 0, 0, 0
    while jobs:
        if jobs[cnt][0] <= i:
            wait += i - jobs[cnt][0]
            i += jobs[cnt][1]
            result += (wait + jobs[cnt][1])
            del jobs[cnt]
            cnt, wait = 0, 0
        else:
            cnt += 1
    return result // length

- 보통 런타임 에러가 나는 이유는 다음과 같다고 한다.

1. 배열에 할당된 크기를 넘어서 접근했을 때
2. 전역 배열의 크기가 메모리 제한을 초과할 때
3. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
4. 0으로 나눌 때
5. 라이브러리에서 예외를 발생시켰을 때
6. 재귀 호출이 너무 깊어질 때
7. 이미 해제된 메모리를 또 참조할 때
8. 프로그램(main 함수)이 0이 아닌 수를 반환했을 때

# 고찰

- 내 풀이의 경우 jobs를 처리 소요시간 순으로 정렬하고 아무것도 고려하지 않고 바로 시간을 쭉 더해서 문제를 해결하려 했다.

- 그러나 해당 문제에서는 다음과 같은 조건을 고려해서 알고리즘을 설계해야 한다.

1. 현재 시점에서 처리할 수 있는 작업인지 판별하고, 처리할 수 있는 작업들만 따로 처리한다.
2. 그 후 현재 시점에서 처리할 수 있는 작업이 없으면 다음 시점으로 넘어간다.

- 요청 시간이 '0 이상'이라는 조건도 고려해서 시작 시간을 -1로 잡는 것이 좋다.

 

# 수정한 풀이

import heapq

def solution(jobs):
    count, last, answer = 0, -1, 0
    heap = []
    jobs.sort()
    
    # 시작시간 초기화
    time = jobs[0][0]
    while count < len(jobs):
        for s, t in jobs:
            if last < s <= time:
            
                # 작업 소요시간으로 min heap을 만들기 위해 (t, s) 푸시
                heapq.heappush(heap, (t, s))
                
        # 바로 수행할 수 있는 작업이 있는 경우
        if len(heap) > 0:
            count += 1
            last = time
            term, start = heapq.heappop(heap)
            time += term
            answer += (time - start)
            
        # 바로 수행할 수 있는 작업이 없는 경우
        else:
            time += 1
    return answer // len(jobs)

- 미리 정렬하는 sort를 사용하는 대신 힙(heap)을 사용하여 처리 가능한 작업들에 대해 작업 소요시간 순으로 정렬한 다음 문제를 해결했다.

- 힙 구조에 대한 미숙과 문제 알고리즘 설계 능력이 부족했던 문제였다.