프로그래머스 Lv.3 | Python | 디스크컨트롤러

1. 문제 정보

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

프로그래머스

 

• 난이도: Lv.3

---

2. 문제 설명

하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정합니다. 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.

1. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.
2. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
3. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
4. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.

 

제한 조건

• 1 ≤ jobs의 길이 ≤ 500
• jobs[i]는 i번 작업에 대한 정보이고 [s, l] 형태입니다.
• s는 작업이 요청되는 시점이며 0 ≤ s ≤ 1,000입니다.
• l은 작업의 소요시간이며 1 ≤ l ≤ 1,000입니다.

---

3. 접근 기준

작업은 시간에 따라 계속 들어오고, 그때마다 어떤 작업을 선택하느냐에 따라 전체 대기 시간이 달라진다.

현재 시점에 대기 중인 작업 중 처리시간이 가장 짧은 작업을 선택하는 방식으로 접근한다

---

4. 사용한 패턴 / 알고리즘

• 최소 힙(min-heap) + 시뮬레이션
  
  • 요청시간 기준으로 작업 관리
  • 처리시간 기준으로 우선순위 큐 구성

“시간 흐름에 따라 작업을 추가하고, 최소 힙으로 가장 짧은 작업을 선택하는 구조”

---

5. 핵심 아이디어

• 작업을 요청시간 기준으로 정렬
• 현재 시간까지 도착한 작업을 힙에 추가
• 힙에서는 처리시간이 가장 짧은 작업을 선택
• 작업 수행 후, (현재시간 - 요청시간)을 누적
• 작업이 없으면 시간을 다음 요청시간으로 이동

---

6. 풀이 코드

초기코드

import heapq
def solution(jobs):
    answer = 0
    time = 0
    ans = []
    for i in range(len(jobs)):
        ans.append(jobs[i]+[i])
        ans[i][0],ans[i][1] = ans[i][1], ans[i][0]
    ans.sort(key=lambda x : x[1])
    
    heap = []
    idx = 0
    total =0 
    while idx<len(ans) or heap:
        while idx<len(ans) and ans[idx][1]<=time:
            heapq.heappush(heap, ans[idx])
            idx+=1

        if heap :
            duration, start, _id = heapq.heappop(heap)
            time += duration
            total += time - start
        else:
            time +=1

    return int(total/len(jobs))​

 

 

최적화 코드

import heapq

def solution(jobs):
    jobs.sort()  # 요청시간 기준 정렬
    
    heap = []
    time = 0
    idx = 0
    total = 0
    n = len(jobs)
    
    while idx < n or heap:
        
        # 현재 시간까지 들어온 작업 push
        while idx < n and jobs[idx][0] <= time:
            start, duration = jobs[idx]
            heapq.heappush(heap, (duration, start))
            idx += 1
        
        if heap:
            duration, start = heapq.heappop(heap)
            time += duration
            total += time - start
        else:
            # 다음 작업 시작 시간으로 점프
            time = jobs[idx][0]
    
    return total // n​

---

7. 핵심 로직 요약

1. 요청시간 기준 정렬 후, 현재 시간까지 도착한 작업을 힙에 추가
2. 힙에서 처리시간이 가장 짧은 작업을 선택하여 수행
3. (현재시간 - 요청시간)을 누적하여 평균 계산

---

8. 개선점

• time을 +1씩 증가를 시키면서 모든 시간을 탐색했는데, heap이 비었는 경우 바로 다음 작업의 time으로 점프를 하면 더 효율적인 코드 작성이 가능하다.
• 문제 조건에 작업번호도 우선순위에 포함이 되지만 평균시간에는 영향이 없기 때문에 따로 추가를 하지 않아도 문제 풀이가 가능하다.

---