[알고리즘 분석 #6] 디스크 컨트롤러 프로그래머스 Python

사용 알고리즘

우선순위 큐

사용 자료구조 특징

1. Heap 기반 자료구조이다
2. Heap 은 일반적으로 완전 이진트리 구조를 가지고 있다. 
3. 우선순위 큐는 우선순위가 높은 원소부터 처리된다. -> 넣으면 이진트리 형태로 들어가서 찾기, 변경하기가 O(log N)
4. 큐에 넣을때 자동으로 정렬된다.
5. python Heapq는 기본은 최소힙이다 ( 가장 작은 값이 부모노드 이다) ( 배열 맨 첫번째 요소 )

파악하는 방법 ( 풀이를 고민하는 흐름 방식 )

우선 모든 방법을 찾는다는 생각을 버린다
현재 시간에 따라서 어떤 디스크가 올지 고민해야한다 (  실행시간이 짧은게 우선적으로 실행되야하는것을 안다면 더욱 좋다 )

현재 시간에 따라 -> 어떤 디스크가 옳을지 -> 를 무한반벅

따라서 현재시간 기점으로 여러개의 디스크가 가능하다고 가정했을때 어떤 판단을 할지 결정해야한다. 

우선순위큐는 여러개의 디스크를 판단하는데 도움을 주는 자료구조기 때문에 여기서 힌트를 얻는게 맞다

푸는 방법 ( CODE )

import heapq

def solution(jobs):
    # 요청 시간순으로 정렬
    jobs.sort()
    n = len(jobs)
    # 현재 시간
    time = 0
    queue = []
    count = 0
    total_time = 0
    while count < n:
        # 현재 시간 이전에 요청된 작업들을 대기열에 삽입
        while jobs and jobs[0][0] <= time:
            request, duration = jobs.pop(0)
            heapq.heappush(queue, (duration, request)) # 소요시간이 작은것부터 넣기 위해
        
        # 현재 시간전에 실행 가능한(요청시간보다 뒤에) 디스크가 있다면
        if queue:
            duration, request = heapq.heappop(queue)
            wait_time = time - request # 현재시간 - 요청 시간
            total_time += wait_time + duration # 소요되는시간 더하기
            time += duration # 현재시간 갱신
            count += 1

        else:
            # 현재 시간전에 시작되는 디스트가 없다면 현재시간 갱신
            time += 1
            
    # 작업의 요청부터 종료까지 걸린 시간의 평균 계산
    answer = total_time // n
    return answer

ETC..

자료구조가 Heap 인데, 완전 이진트리 형태를 가지고 있음으로, 완전 이진트리인지 확인하는 문제에서 사용해도 될 것 같다

https://nobilitycat.tistory.com/entry/%ED%9E%99Heap%EA%B3%BC-%EC%99%84%EC%A0%84-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%ACComplete-binary-tree

힙(Heap)과 완전 이진 트리(Complete binary tree)

미래의 내가 또다시 읽어본다면 좋을듯 싶다.