[프로그래머스/Python] Level 3_디스크 컨트롤러

📌문제 유형

힙(heap)

 

📌문제

프로그래머스

 

📌나의 문제풀이

- 40점

import heapq

def solution(jobs):
    answer = 0
    keep_times = []
    heapq.heapify(jobs)
    # print(jobs)
    
    now, cnt = 0, 0
    while jobs:
        if cnt == 0:
            disk = heapq.heappop(jobs)
            keep_times.append(disk[1])
            now = disk[1] + disk[0]
        else:
            # 현재시간 기준으로 없으면? 다음 것 진행
            if now < jobs[0][0]:
                disk = heapq.heappop(jobs)
                keep_times.append(disk[1])
                now = disk[1] + disk[0]
            
        # [현재 시간 기준, 작업 가능한 대상 중 소요시간 짧은 것]
        # 작업 가능한 대상 고르기
        tmp = []
        while jobs:
            a = heapq.heappop(jobs)
            if a[0] <= now:
                heapq.heappush(tmp,[a[1],a[0]])
            else:
                heapq.heappush(jobs,a)
                break
            
                
        # 소요시간 짧은거 고르기
        # tmp는 [작업의 소요 시간, 작업 요청되는 시점]으로 저장
        while tmp:
            next_time, next_start = heapq.heappop(tmp)
            keep_times.append((now - next_start) + next_time)
            now += next_time    # 한 번 하고 다시 되돌아가야하는거?
        
        cnt += 1
    
    return sum(keep_times) // len(keep_times)

 

- 통과

- 놓치고 있었던 아이디어

• now는 계속 업데이트 됨 -> 업데이트 될 때마다 tmp 다시 설정 -> tmp 반복문 없애기
• tmp == [] 일 경우 인덱스 에러 -> tmp != [] 조건문 넣어주기

import heapq

def solution(jobs):
    answer = 0
    keep_times = []
    heapq.heapify(jobs)
    # print(jobs)
    
    now, cnt = 0, 0
    while jobs:
        if cnt == 0:
            disk = heapq.heappop(jobs)
            keep_times.append(disk[1])
            now = disk[1] + disk[0]
        else:
            # 현재시간 기준으로 없으면? 다음 것 진행
            if now < jobs[0][0]:
                disk = heapq.heappop(jobs)
                keep_times.append(disk[1])
                now = disk[1] + disk[0]
            
        # [현재 시간 기준, 작업 가능한 대상 중 소요시간 짧은 것]
        # 작업 가능한 대상 고르기
        tmp = []
        while jobs:
            a = heapq.heappop(jobs)
            if a[0] <= now:
                heapq.heappush(tmp,[a[1],a[0]])
            else:
                heapq.heappush(jobs,a)
                break
            
        # 소요시간 짧은거 고르기
        # tmp는 [작업의 소요 시간, 작업 요청되는 시점]으로 저장
        if tmp != []:
            next_time, next_start = heapq.heappop(tmp)
            keep_times.append((now - next_start) + next_time)
            now += next_time    # 한 번 하고 다시 되돌아가야하는거? oo

        # tmp에 남아 있는 것 다시 넣기
        if tmp != []:
            for time, start in tmp:
                heapq.heappush(jobs, [start, time])
        
        cnt += 1
    
    return sum(keep_times) // len(keep_times)

 

📌다른사람의 문제풀이

- deque로 풀이

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)

 

📌리뷰

- 핵심 아이디어 : '작업 가능한 대상 중' 소요시간 짧은 순서

• 해당 질의와 동일하게 접근

프로그래머스

- 왜 소요시간 짧은 순서부터?

• 소요시간 짧음 = 나중에 기다리는 시간 짧음

- heap : 최소거리 힙, 가장 작은 것부터 pop으로 나옴

[Python] 파이썬 Heapq 모듈 사용하기 / 힙(Heap) 구조