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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

작업의 평균 시간을 줄이기 위해서 현재 대기하는 작업들의 개수를 최대한 줄여주어야 합니다.

그래서 최소힙을 이용하여 작업이 시작되는 순서대로 작업을 가져왔습니다.

작업을 처리할 수 있는 경우에 대기 명단에 넣었고, 작업이 빨리 끝나는 순서대로 작업을 완료하였습니다.

2) 알고리즘

• 최소힙

3) 풀이 코드

사용 언어 - Python

import heapq

def solution(jobs):
    N = len(jobs)                                       # 평균을 구하기 위한 작업의 개수
    heapq.heapify(jobs)                                 # 작업들을 최소힙으로 만듦
    ms = 0                                              # 현재 작업의 시간
    answer = 0                                          # 순수 작업한 시간

    waiting = []                                        # 작업 대기 명단
    while jobs or waiting:                              # 작업이 남아있으면 반복
        while jobs:                                     # 작업이 남아있다면
            task = heapq.heappop(jobs)               
            if task[0] > ms:                            # 현재 작업 요청된 시간의 이전일때
                heapq.heappush(jobs, task)              # 아직 작업 시작 못하므로 다시 작업 내역에 추가
                if not waiting:                         # 대기 명단이 비어 있으면 시간 1ms 흐르기
                    ms += 1
                break
            else:
                heapq.heappush(waiting, (task[1], task[0]))     # 작업이 가능하다면 대기명단에 추가
        
        if waiting:                                     # 대기명단에 작업이 있으면
            task = heapq.heappop(waiting)               # 가장 빨리 끝나는 작업 꺼내기
            answer += ms - task[1] + task[0]            # 작업 소요 시간 추가
            ms += task[0]                               # 작업이 끝났을때 시간으로 정의
    
    return answer//N                                    # 평균

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

처음 풀이하였을때, 작업이 연속적으로 이루어지지 않고, 중간에 비어 있는 경우를 고려하지 못하여 컴파일 오류가 발생했었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

코딩테스트 연습 - 디스크 컨트롤러

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다