[프로그래머스/파이썬] 디스크 컨트롤러

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

프로그래머스

 

정말 오랜만에 알고리즘 문제를 풀었다.

 

요즘 인생의 번아웃이 온 건지 운동이나 여행, 친구 만나기 등 말고는 손에 잡히지도 않고 그냥 빈둥대며 산다.

어제 1월 첫 랩실 세미나 갔다가 열심히 하는 다른 사람들의 모습을 보고 다시 열정의 불씨가 조금씩 지펴진 듯

나도 모르게 알고리즘에 손을 대기 시작했다.

 

문제풀이

1. 우선 굳이 힙을 써도, 안써도 된다

두 방법으로 모두 풀어보았는데, 시간복잡도 측면에서 힙을 사용하는 것이 훨씬 좋으니까

풀이가 막막한 경우 말고는 힙을 써보도록 하자 (리스트로만 풀 땐 예외 조건 몇 개만 잘 검사해주면 금방 풀린다)

 

2. jobs 들을 탐색하며 현재 작업을 시작할 수 있는 것들을 최소 힙에 담아준다.

이 때, 현재 작업을 시작할 수 있는 것들 중 작업시간이 최소인 애들을 먼저 처리해주어야 하므로 최소힙에 넣는 기준을

작업시간으로 설정해준다.

 

왜?? 직관적으로 설명해서, 현재 시작할 수 있는 일들 중 가장 오래 걸리는 일을 먼저 시작한다면 다른 일들은 오래 걸리는 일이 끝날 때까지 무한정 대기상태이다.

디스크에서 무한 대기라는 뜻은 그냥 크롬창 무한 로딩이라고 생각하면 편하다.

 

3. 2번 작업을 통해 힙에 무언가 들어왔다면 가장 최소(= 현재 처리 가능한 작업 중 작업 시간이 최소)인 노드를 꺼내와 걸린 시간, 현재 시간 등을 계산해준다.

그런 다음, i를 1 증가시켜 준다. 하나의 작업에 대해 처리가 끝났고, 우리는 job에 담긴 모든 작업들을 처리해주어야 하므로 i와 len(jobs)을 이용해준다.

i==len(jobs) 를 만족할 때 까지 돌려준다는 의미다.

 

4. 만약 2번 작업을 거쳐도 힙에 아무 것도 없다면, 지금 당장 시작할 수 있는 작업이 없다는 뜻이므로

1ms 기다려준다 (= now+=1) 

import heapq
def solution(jobs):
    answer = 0
    now = 0
    start = -1
    heap = []
    
    i=0
    while i<len(jobs):
    #for i in range(len(jobs)):
        for job in jobs:
            if start < job[0] <= now:
                heapq.heappush(heap,[job[1],job[0]])
        if len(heap)>0:
            current = heapq.heappop(heap)
            start = now
            now += current[0]
            answer += (now - current[1])
            i+=1
        else:
            now += 1
    return answer // len(jobs)