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

어쩌다 두문제 연속 Heap 문제를 풀었는데, 생각만큼 잘 풀리지도 않아서 정리해보는 문제

 

 

해당 문제는 카테고라가 '힙'이라고 적혀져 있는만큼 힙으로 풀어야하는 건 파악했지만,

그럼에도 불구하고 문제를 풀지 못했다..~

 

📌 문제 링크

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

프로그래머스

 

 

 

 

 

💡힙이란?

- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

 

즉, 알고리즘 문제 풀이에서 최댓값, 최솟값을 빠르게 찾아내는 연산을 하기 위해서 사용된다.

힙은 데이터 삽입, 삭제 모두 시간복잡도가 O(log₂ N)이다. 따라서 데이터 처리에 효율적이라고 볼 수 있다.

특히 python의 경우 heapq모듈을 지원하므로 더욱 편리하게 코드를 작성할 수 있다. 

 

간단하게 예제 코드는 다음과 같다

import heapq	#heapq를 사용하기 위해서는 import를 꼭 해줘야한다

heap = []	#heap 초기화


# 삽입 (heap에 14라는 수를 추가한다는 의미이다)
heapq.heappush(heap, 14)
heapq.heappush(heap,8)

#여기까지 실행하면 heap = [8, 14] 가 된다


#heap에서 가장 작은 수를 return 해준다. 즉, 8이 return 된다
heapq.heappop(heap)

#여기까지 실행하면 heap = [14]가 된다


#heap을 list로 변환시켜준다
heapq.heapify(_list)

 

 

그럼 문제로 돌아와보자

해당 문제는 가장 빠르게 일을 끝낼 수 있도록 하는 것이 핵심이다. 

여기서 '작업이 걸리는 시간이 짧은 순으로 작업을 진행해야한다'는 것을 떠올려야한다.'

 

 

👩‍💻 전체코드 1: heap

import heapq

def solution(jobs):
    # 작업 요청부터 종료까지 걸린 시간 answer
    # 현재 시간 now
    # 처리한 일의 갯수 i
    answer, now, i = 0, 0, 0
    
    
    start = -1	#이전 작업 시작 완료 시간
    heap = []
    
    while i < len(jobs):
        for j in jobs:
            #요청 시간이 이전작업의 시작시간 보다 크고, 현재 시간보다 작거나 같은 작업을 최소 힙에 삽입
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])	#작업 걸리는 시간, 시작 시간으로 추가
        
        if len(heap) > 0:   #처리할 작업이 있는 경우 
            cur = heapq.heappop(heap)
            start = now		#시작 시간 현재 시간으로 갱신
            now += cur[0]	#현재 시간에서 작업 소요 시간을 더해 현재 시간 갱신
            answer += now - cur[1] #대기 시간 및 처리 시간 누적
            i += 1 #일 하나 처리했으므로 +1
            
        else:   #처리할 작업이 없는 경우 현재 시간 1 증가
            now += 1
    return answer // len(jobs)

최대한 이해가 쉽도록 주석을 많이 달았다

직접 하나하나 적어가며 계산을 해보면 좀 더 와닿을 것이다

이것저것 신경쓸 시간이 많아서..~ 헷갈리지 않았나하는 생각이 든다

 

 

 

 

👩‍💻 전체코드 2

def solution(jobs):
    answer = 0
    start = 0
    length = len(jobs)

    jobs = sorted(jobs, key=lambda x: x[1])

    while len(jobs) != 0:
        for i in range(len(jobs)):
            if jobs[i][0] <= start:
                start += jobs[i][1]
                answer += start - jobs[i][0]
                jobs.pop(i)
                break
            
            if i == len(jobs) - 1:
                start += 1

    return answer // length

 

또한, 아래의 방식으로 heap을 쓰지 않고 푸는 방법 또한 있다

풀이 방법은 위와 굉장히 유사하지만, 입력받은 job배열을 소요시간 기준으로 정렬을 하고 pop을 하며 계산을 한다는 점이 다르다.