[프로그래밍] 프로그래머스 - 디스크 컨트롤러 [Heap]

https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=python3

프로그래머스

 

오랜 기간 동안 문제를 잘 풀지 못해, 결국 블로그, 영상 등을 참고해 겨우 따라간 문제. 

 

우선 강의는 아래 이 분 것을 참고하였음. 
https://www.youtube.com/watch?v=qA-wy00bQv4

 

문제를 보면, 가장 적은 대기 시간이 되도록 업무를 스케줄링 하는것을 의미한다.

나는 이게 바로 heap으로 푸는 건지 긴가민가 했는데, "소요 시간"을 기준으로 task를 배정하는 문제이기 때문에 heap을 사용하는 유형이라고 한다. 이런 건 조금 더 문제 풀면서 익숙해져야겠다.

우선 먼저 다음과 같은 업무가 있으면 이를 시작 시간을 기준으로 정렬을 수행한다. 
( 왜냐면 그래도 요청 시간이 빠른 업무부터 먼저 처리하는 것이 불필요한 기다리는 시간을 낭비하지 않게하기 때문이다. 어쩌면 당연하다 )

위 그림처럼 주어진 리스트에서 빨간색 표시한 부분이 시작 시간이고 이를 기준으로 정렬하면 위와 같이 배치된다. 

자 그럼 여기서 현재 처리하는 시간 기준으로 앞으로 나온 task들을 "소요 시간"을 기준으로 heap에 배치하는데

예를 들어 [0,3]을 수행하고 있으면 나머지는 소요 시간을 기준으로 heap으로 자동 배정되는 것이다. 

자 그런데 여기서 중요한 점은 저 [1,9] 나 [2,6] 이 대기열로 등록이 되는데 예를 들어 다음과 같은 극단적인 케이스가 있다고 해보자. 

[0,3] task를 수행하면 끝나는 시간이 3이라 현재 3ms에 해당하는 위치에 있지만 다음 task 는 4ms이기 때문에 대기열이고 뭐고 간에 우선 기다려야 한다. 이런 경우에는 현재 끝나는 시간 (3ms) 이나 그 전에 이미 요청이 되서 (1ms나 2ms때 이미 요청된) 기다리고 있는 task는 먼저 대기열에 넣어주되, 저렇게 아직 시간이 오지 않는 애들은 우선순위에서 밀릴 수 밖에 없다. 따라서 저 경우는 요청 시간이 올때까지 기다려야 하는 점을 명심해야 한다. 

조금 더 그림으로 직관적으로 표현하면 

다음과 같이 노란색 부분이 현재 처리하는 task이고, 이것이 끝날 시간 (3ms) 기준으로 그 전에 이미 요청된 (1ms, 2ms) 경우는 바로 heap으로 넣어서 소요 시간 기준 스케줄링을 수행하는 반면

다음과 같이 4ms로 대기하는 경우 1ms를 더 대기하는 시간이 포함되게 된다. 이 경우는 아직 heap 대기열에 추가되는 경우가 아니다. 즉, 이런 경우를 잘 구별해서 조건문을 구성해야 한다. 

구성한 코드는 아래와 같다. 

import heapq as hp

def solution(jobs) :
    jobs = sorted(jobs)

    current_pos = -1; end_time = 0 ## 시작점 잡는 것도 연습해야

    heaps = [] ## 대기 중인 작업들 (소요시간 기준으로 heap 구성)

    cnt = 0; answer = 0

    while cnt < len(jobs) :
        ### 현 시점 기준으로 앞으로 진행할 테스크 중 소요 시간 적은 순으로 heap 구성
        for start, time in jobs :
            if current_pos < start <= end_time :
                hp.heappush(heaps,[time,start])

        ### 현 시점 task가 끝나고 이미 대기열 중인 애들이 있다면 먼저 추출
        if heaps :
            current_pos = end_time
            time, start = hp.heappop(heaps)
            end_time += time
            answer += (end_time-start)
            cnt += 1

        ### 아직 요청 시간이 다다르지 못할 때는 요청시간 대기열에 들어올 때 까지 시간 소요
        ### 여기 부분도 시간이 지나간다    
        else :
            end_time += 1

    return answer//len(jobs)

 

즉, 현재 task의 끝나는 시간(end_time)과 현재 위치(current_pos), 그리고 대기 task의 요청된 시점 (start)과 시간(time) 등을 잘 tracking하는 것이 중요하다.

필자의 경우 첫 task도 적용할 수 있는 ( 본 예제의 경우 [0,3] ) 조건을 짜는 게 힘들었는데 영상을 보니, 현재 task의 끝나는 시간을 0, 시작 시간을 -1로 가상 task를 붙여서 하는 경우처럼 문제를 구성했는데 이런 아이디어에 익숙해져야겠다.

즉, 이 문제가 "소요 시간"을 기준으로 정렬을 수행하는 Heap을 사용한다는 점에 익숙해지고
이런 대기 시간 기준 heap을 통해 최적의 스케줄링을 계산하는 문제 유형에 익숙해지자.