[힙(Heap)] Level 3 디스크 컨트롤러 - Python

요즘 너무 정신이 없다,,

괜히 욕심부려서 알바를 늘렸더니 너무 피곤해 ㅜㅅㅜ

원래 코테도 매일매일 꾸준히 했는데 프로젝트 시작하고 일주일에 2-3문제 풀까말까네,,

얼른 체력 좀 기르자!!

암턴 이러한 이유들로 이 문제는 파이썬만 구현했다ㅠㅠ

생각보다 어려워서 다른 사람들 코드를 참고해서 풀었다,,,에혀,,

---

문제 설명

• 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다.
• 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다.
• 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다.

 

예를 들어

 

 

제한 사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

 

입출력 예시

---

풀이)

이거 왜 어렵지?

괜히 운체생각나서 그런가,,,

아무튼 계속 고민하다가 힙을 잘 몰라서 그런지 어쩐지 감이 안와서 다른 분들의 코드를 찾아보았다🙇‍♀️

 

풀이 방법은 아래와 같다

먼저 현재 시점에서 처리할 수 있는 작업들을 모두 힙에 넣는다

그리고 하나를 뽑아 현재 시점과 총 대기시간을 구해주는 것을 모든 작업을 처리할 때까지 반복한다

 

이 때 힙에 push를 할 떄는 작업의 처리시간이 기준으로 최소힙이 만들어져야하기 떄문에 [ 작업 처리 시간, 작업 요청 시간 ] 순서로 넣어준다

 

만약 작업의 요청 시간이 바로 이전에 완료한 작업 시작 시간(start)보다는 크고, 현재 시점(now)보다 작거나 같아야 한다

-> start로 이미 처리된 작업들은 쳐내고, now로 요청이 들어온 작업들만 가져오도록 하는 거임!

 

만약 현재 처리할 수 있는 작업이 없다면, 남은 작업들이 아직 요청되지 않은 거니까 현재 시점(now)를 1을 더해준다

 

자 바ㅏㅏㅏㅏ로 코드!

수빙수님,, so cute😭

 

 

파이썬 코드)

import heapq
def solution(jobs):
    answer = 0 # 작업하는데 걸린 총 시간
    now = 0 #현재 시간(시점)
    i = 0 #처리된 작업의 개수
    start = -1 # 이전에 완료한 작업의 시작 시간
    heap = [] #현재 처리 가능한 jobs을 담는 힙
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now: # 이전에 끝낸 작업보다 큰 시간이고, 현재 시점보다 작은 시간인 경우 작업 가능
                heapq.heappush(heap, [j[1], j[0]]) # (처리 시간, 요청 시간)
        
        if len(heap) > 0: # 힙에 처리할 작업이 남은 경우
            current = heapq.heappop(heap) #cur은 현재 처리중인 작업
            start = now
            now += current[0]
            answer += (now - current[1]) # 작업 요청시간부터 처리 완료까지의 시간 계산
            i += 1
        else: # 처리할 작업이 없는 경우
            now += 1
            
    answer = answer // len(jobs) # 평균 처리 시간 계산
    
    return answer

짠!

위의 알고리즘대로 구현했다!

흠 start랑 now를 생각하기가 힘들었던 것 같아

i로 처리된 작업 수를 구해서 while 반복문 탈출하도록 했고

마지막 answer return하기 전에 평균 값을 return해야 되니까 jobs 개수만큼 나눠주고 return 한다!

 

c++은 아쉽지만,,, 다음에,,,

그럼 빠잉,,,