[프로그래머스][LV.3] 디스크 컨트롤러 | python3

문제링크:  디스크 컨트롤러

 

---

문제설명

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

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

 

예를 들어

- 0ms 시점에 3ms가 소요되는 0번 작업 요청
- 1ms 시점에 9ms가 소요되는 1번 작업 요청
- 3ms 시점에 5ms가 소요되는 2번 작업 요청

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

이 요청을 우선순위 디스크 컨트롤러가 처리하는 과정은 다음 표와 같습니다.

모든 요청 작업을 마쳤을 때 각 작업에 대한 반환 시간(turnaround time)은 작업 요청부터 종료까지 걸린 시간으로 정의합니다. 위의 우선순위 디스크 컨트롤러가 처리한 각 작업의 반환 시간은 다음 그림, 표와 같습니다.

우선순위 디스크 컨트롤러에서 모든 요청 작업의 반환 시간의 평균은 8ms(= (3ms + 16ms + 5ms) / 3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해 주세요.

제한조건

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

---

 

문제풀이

찾아보며 풀었다.

시간을 체크하는 변수를 만들어야 할 거 같은데 풀리지가 않았다.

 

시간을 체크하는 변수가 2개 있어야 했다,

현재 시간과 작업이 끝난 시점의 시간.

 

나의코드

import heapq as hq

def solution(jobs):
    answer = 0
    # 현재시점
    now_time=0
    # i번째 작업
    i=0
    
    start=-1 # 작업을 완료한 시간 => 작업 시작 시간
    heap=[]
    
    while i < len(jobs):
        
        # 현재 시점에서 처리할 수 있는 작업 heap에 저장
        # jobs[요청시간,소요시간]
        for j in jobs:
            if start < j[0] <=now_time: # start로 인해 그 전에 추가된 작업들은 걸러짐
                hq.heappush(heap,[j[1],j[0]]) # 소요시간 기준이기 때문에 순서를 바꿔줌
        
        if len(heap) > 0: # 처리할 수 있는 작업이 있을 경우
            cur = hq.heappop(heap)
            start=now_time
            now_time+=cur[0] # 소요시간 추가 :: 작업에 한 번 들어가면 끝날때까지 다른 작업은 하지 않기 때문
            answer+=now_time-cur[1] # 작업 요청시간부터 종료시간가지의 시간 계산
            i+=1
        else: # 처리할 작업 없으면 :: 현재 시간만 1 흐름
            now_time+=1
    
        
    return answer//len(jobs)

 

---

 

참고하기

import heapq
from collections import deque

def solution(jobs):
    tasks = deque(sorted([(x[1], x[0]) for x in jobs], key=lambda x: (x[1], x[0])))
    q = []
    heapq.heappush(q, tasks.popleft())
    current_time, total_response_time = 0, 0
    while len(q) > 0:
        dur, arr = heapq.heappop(q)
        current_time = max(current_time + dur, arr + dur)
        total_response_time += current_time - arr
        while len(tasks) > 0 and tasks[0][1] <= current_time:
            heapq.heappush(q, tasks.popleft())
        if len(tasks) > 0 and len(q) == 0:
            heapq.heappush(q, tasks.popleft())
    return total_response_time // len(jobs)

 

import heapq


class Job(object):
    def __init__(self, begin=0, cost=0):
        self.begin = begin
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

    def __le__(self, other):
        return self.cost <= other.cost


def solution(jobs):
    jobs.sort(key=lambda item: item[0])

    last_index = 1
    job_heap = [Job(begin=jobs[0][0], cost=jobs[0][1])]
    current_time = jobs[0][0]
    answer = 0
    while True:
        while last_index < len(jobs) and jobs[last_index][0] <= current_time:
            job = Job(begin=jobs[last_index][0], cost=jobs[last_index][1])
            heapq.heappush(job_heap, job)
            last_index += 1

        if len(job_heap) == 0:
            if last_index < len(jobs):
                job = Job(begin=jobs[last_index][0], cost=jobs[last_index][1])
                current_time = job.begin
                heapq.heappush(job_heap, job)
                last_index += 1
            else:
                break

        next_job = heapq.heappop(job_heap)

        current_time += next_job.cost

        answer += (current_time - next_job.begin)

    answer = int(answer/len(jobs))
    return answer