디스크 컨트롤러

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

★다시 풀어봐야할 문제★ (풀긴풀었는데 너무 지저분하게 푼 느낌, 현재시간 업데이트를 간단한 방식으로 구현해보기)

문제 파악 [필수 작성]

문제이해

적절히 작업건들을 배치하여서
평균작업완료대기시간의 최소시간을 구하는 문제

제한 조건 확인

소수점 이하의 수는 버림 (버리는 커맨드? 나중에 찾아보기)
최대 500개의 job
0~1000 작업이 들어올 수 있는 시간대
작업이 쌓이지 않았을 경우에는 먼저 들어온 요청부터 처리

아이디어

평균작업완료대기시간이 최소화 되려면
하드디스크가 이미 점유되어있을때
하드디스크가 점유된 작업을 끝내는 순간에
예약된 작업들 중 가장 작업시간이 짧은 작업부터 쳐내야한다.
왜냐면 아무리 오래 기다린 작업이라도 작업시간이 길면
나머지 작업들도 다 그만큼 오버헤드가 늘어나기 때문이다.

그냥 min_heap 으로 간단히 구현만 하면 되는 문제
하드디스크가 기존작업에 의해 점유되어있는지 여부만 잘 확인하면 되는 문제
하드디스크가 일을 끝낸시점에 아주짧은 태스크가 들어올 수 있음

각 작업이 얼마나 기다렸는지도 기록해야함

jobs 길이 저장
jobs 를 sort 후
deque 로 변환

점유끝시간 = 0

jobs 에 없을때까지
요청시각, 작업시간 = jobs.popleft
만약 요청시각 < 현재 점유끝시간 이면: # 지금 작업을 하고 있는 상태
min_heap 에 (작업소요시간,요청시각) 순으로 heappush

만약 요청시각 >= 현재 점유끝시간 이면: # 현재 작업하고 있는게 없는 상태
    min_heap 에 (작업시간,요청시간) 순으로 heappush
    작업소요시간, 요청시각 = min_heap 에서 heappop
    (현재 점유 끝시간 - 요청시각 + 작업 소요시간)을 총 완료대기시간 누적합에 더함
    다음 점유끝시간 = 작업소요시간 + 현재 점유끝시간

min_heap에 없을때까지
작업소요시간, 요청시각 = min_heap 에서 heappop
(현재 점유 끝시간 - 요청시각 + 작업 소요시간)을 총 완료대기시간 누적합에 더함
다음 점유끝시간 = 작업소요시간 + 현재 점유끝시간

리턴 int(완료대기시간 누적합 // jobs 갯수)

시간복잡도

최대 500개 이기때문에
heap 삽입&삭제 최악의 경우에도
O(nlogn) -> 시간 널널

자료구조

현재시각을 나타내는 int 형 정수
총 대기시간 누적합을 나타내는 int 형 정수

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

1차 시도 (1시간 소요)

코드 로직 자체가 잘못됨, list sort 한거 순차적으로 꺼내면 안됨.
lock 이 풀리는시점까지 쌓인것중 가장 빠르게 처리할 수 있는거부터 꺼내야됨.
제출하지 않고 코드로직 잘못된거 알음.
아예 갈아엎어야 됨.

import heapq
from collections import deque

def solution(jobs):
    
    min_heap = []
    jobs.sort()
    deque_jobs = deque(jobs)

    tmp_unlock_timing = 0
    waiting_time_sum = 0
    # print("deque_jobs:",deque_jobs)
    while deque_jobs:
        requested_at, working_time = deque_jobs.popleft()
        if requested_at < tmp_unlock_timing: # 지금 작업을 하고 있는 상태
            heapq.heappush(min_heap,(working_time,requested_at))
        elif requested_at >= tmp_unlock_timing: # 현재 작업하고 있는게 없는 상태
            heapq.heappush(min_heap,(working_time,requested_at))
            working_time,requested_at = heapq.heappop(min_heap)
            if requested_at <= tmp_unlock_timing:
                waiting_time_sum += tmp_unlock_timing - requested_at + working_time
                tmp_unlock_timing += working_time
            else:
                waiting_time_sum += working_time
                tmp_unlock_timing = requested_at + working_time
        # print("=================================")
        # print("tmp_unlock_timing:",tmp_unlock_timing)
        # print("requested_at:",requested_at)
        # print("working_time:",working_time)
        # print("waiting_time_sum:",waiting_time_sum)
        # print("=================================")
        
    print("min_heap:",min_heap)
    while min_heap:
        working_time,requested_at = heapq.heappop(min_heap)
        waiting_time_sum += tmp_unlock_timing - requested_at + working_time
        tmp_unlock_timing += working_time

    return waiting_time_sum//len(jobs)

2차 시도 (고치는데 1시간소요)

추가했던 테스트 케이스

[[0, 3], [6, 9], [6, 6]] - 8

[[0, 3], [6, 9], [6, 6], [9, 6]] - 9

[[0, 3], [6, 9], [6, 6], [9, 6], [100, 1]] - 8

예약된거중 작업시간순 으로 처리하는게 핵심

근데 코드가 전체적으로 너무 복잡한 간단한 방법으로 다음에 다시 풀어보기

import heapq
from collections import deque

def solution(jobs):
    
    min_heap = []
    jobs.sort()
    deque_jobs = deque(jobs)
    
    tmp_unlock_timing = 0
    waiting_time_sum = 0
    
    for deque_job in deque_jobs:
        flag = 0
        tmp_requested_at, tmp_working_time = deque_job
        while min_heap:
            if tmp_unlock_timing < tmp_requested_at:
                next_working_time, next_requested_at = heapq.heappop(min_heap)
                waiting_time_sum += tmp_unlock_timing - next_requested_at + next_working_time
                tmp_unlock_timing += next_working_time
            else:
                heapq.heappush(min_heap,(tmp_working_time,tmp_requested_at))
                flag = 1
                break
        if flag == 1:
            continue
        elif tmp_unlock_timing <= tmp_requested_at:
            waiting_time_sum += tmp_working_time
            tmp_unlock_timing = tmp_requested_at + tmp_working_time
        else:
            heapq.heappush(min_heap,(tmp_working_time,tmp_requested_at))
                
    while min_heap:
        working_time,requested_at = heapq.heappop(min_heap)
        if requested_at <= tmp_unlock_timing:
            waiting_time_sum += tmp_unlock_timing - requested_at + working_time
            tmp_unlock_timing += working_time
        else:
            waiting_time_sum += working_time
            tmp_unlock_timing = requested_at + working_time

    return waiting_time_sum//len(jobs)

배우게 된 점 [필수 작성]

버림 → math.floor
올림 → math.ceil

반올림 → round

floor, ceil 이 함수명이 기억안나서 그냥 int 형변환 씀..

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.