[프로그래머스 42627 파이썬] 디스크 컨트롤러 (level 3, 힙)

알고리즘 유형 : 힙, 그리디
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import heapq

def solution(jobs):
    # answer : 답
    # cnt_time : 현재 위치한 시간
    # 처리한 작업의 개수
    answer, cnt_time, i = 0, 0, 0
    
    # 가장 최근에 처리한 작업의 처리 시작 시간
    start = -1
    
    # 요청이 들어온 작업들을 담아두는 최소 힙
    process = []
    
    # 모든 작업 처리할 때 까지 반복
    while i < len(jobs):
        # 현재 시간인 cnt_time(가장 최근 작업 처리 끝나고 난 시간)과
        # 가장 최근에 처리된 작업의 처리 시작 시간인 start에 대해,
        # 가장 최근 작업을 처리하는 동안 요청이 들어온 작업이 있는 지
        # 탐색하고 그 것들을 힙에 넣어두는 구문
        for job in jobs:
            if start < job[0] <= cnt_time:
                heapq.heappush(process, (job[1], job[0]))
        
        # 만약 힙에 처리해야 할 작업이 있는 경우 처리
        # 없다면 그냥 시간 1ms 더해줌
        # 우선순위가 높은 작업을 힙에서 꺼내고,
        # 이 구문에서 현재 꺼낸 작업을 처리하고,
        # 소요 시간을 answer에 더하고,
        # 곧바로 작업 끝나는 지점의 시간으로 점프하는 작업을 할 것임.
        # 따라서, start를 현재 위치로 정하고(뽑은 작업의 처리 시작 시간)
        # cnt_time을 처리 종료 시점인 (cnt_time + 현재 작업 소요 시간)으로 설정
        # 이러고 나면 이제, 뽑은 작업을 처리시키고 시간도 계산해낸 다음
        # 곧바로 다음 작업을 뽑아서 처리하고자 하는 상태가 되게 된다.
        if process:
            job = heapq.heappop(process)
            start = cnt_time
            cnt_time += job[0]
            answer += cnt_time - job[1]
            i += 1
        else:
            cnt_time += 1
    
    return answer // len(jobs)

풀이 요약

1. 그리디와 힙을 사용하는 문제이다.

   한 작업을 끝낸 직후, 그 간 요청이 들어온 작업들 중 소요 시간이 가장 짧은 것을 고르면 최적해를 구할 수 있음을 테스트 케이스를 통해서 확인해볼 수 있고, 제출해보면 모든 테스트 케이스에 대해 성립하므로 일반해를 구할 수 있게 된다. 따라서 그리디 개념을 적용한다.

   작업을 처리하는 동안 요청이 들어온 작업들을 모두 어딘가에 담아뒀다가, 현재 작업의 처리가 끝나고 난 직후 다음 처리할 작업을 골라야하는데, 이 때 담아둔 곳에서 바로 최소 소요 시간의 작업을 뽑아야 한다. 넣을 때마다 매 순간 바로바로 최소 소요 시간 작업을 뽑을 수 있도록 저장해두는 자료구조. 즉 힙을 사용하면 제격임을 알 수 있다.

2. 변수 i를 통해, 모든 작업이 처리될 때까지 while문을 반복한다.

   반복문 각 단계에서 수행할 내용을 알아보자.

   각 단계에서 초기 상태는 어떠한 작업을 끝마치고 난 직후. 이제껏 요청이 들어왔던 작업이 하나라도 있으면 그 것들 중 우선순위 젤 빠른 걸 하나 골라서 처리해주고, 아니면 그냥 그대로 1ms를 흘려보내야하는 상태이다.

   즉 다음 단계에서의 초기 상태는 전 단계에서 작업을 처리하고 난 "직후"임을 유의하자.

   
   이제 필요한 변수들을 생각해보자. 이제껏 들어온 요청이 있는지 탐색하기 위해, 최근에 끝마친 작업의 시작시간부터 끝나는 시간 사이에 요청이 들어온 작업을 jobs를 모두 돌면서 조건문으로 걸러낼 것이다. 이를 위해 필요한 것은 최근에 처리된 작업의 시작 시각과 끝난 시각이다. 최근 처리된 작업 시작 시각을 start, 끝난 시각을 cnt_time으로 둔다.(현재 상태가 최근 작업을 끝마친 직후이므로 current의 의미를 담아 네이밍을 했다.)

   요청이 들어온 모든 작업들을 힙에 담아두었으니, 이제 힙에 작업이 들어있다면 우선순위 젤 높은 작업 하나를 꺼내 처리해주고, 없으면 그대로 시간을 1ms 보내면 된다.

   만약 들어있다면, 힙에서 작업 하나를 꺼내서, 그 작업을 처리하고 난 직후까지를 한 구문으로 처리해준다.

   현재 새 작업을 시작하는 시간이 cnt_time이므로, 이걸 start에 할당해준다.

   그리고 끝나는 시점은 현재 시각에 작업의 소요 시간을 더해준 값이 된다.

   이 후 answer에 해당 작업의 소요 시간(요청 들어온 시점 ~ 끝나는 시점)을 더해주고 i += 1 해준다.

3. 마지막에 평균을 연산하여 리턴해주면 끝!

4. 테스트 케이스로 예를 들어보자.

   작업 A를 처리하고 난 직후, 다음 while 단계에서의 초기 상태는 start = 0, cnt_time = 3, i += 1 이다.

   이 때 A를 처리하는 동안 요청이 들어온 작업들을 이번 단계에서 탐색 후 힙에 넣어줘야된다.

   jobs를 모두 돌면서, 요청 시간이 start와 cnt_time 사이인 것을 모두 넣으면 된다. 요청 시간이 cnt_time인 경우도 지금 당장 처리할 수 있는 작업이므로 등호가 들어가 있다. 이로 인해 start는 전 단계에서 고려된 부분이므로 등호가 없다.

   아무튼, 이제 힙에는 B와 C가 들어있게 된다.

   최소 힙이므로 우선순위는 소요 시간이 적은 C가 높다.

   따라서 C를 뽑고, start = 3, cnt_time = 3+6 = 9로 설정한다.

   C의 처리 시간은, 요청 시간 2부터 종료 시간 9까지 7이다.

   작업 하나를 처리했으므로 i에 1을 더해준다.

배운 점, 어려웠던 점

• 처음에 풀이를 구상할 때, 매 순간 어떤 작업을 먼저 처리해야되는지 고민해보았고, 테스트 케이스를 직접 따라가면서 생각해보니 처리 시간이 가장 짧은 것을 우선적으로 선택해 처리하는게 최적해를 보이길래 그리디 개념을 적용하고자 했다.

  그리고 현재 작업을 진행하면서, 요청이 들어오는 작업을 모두 받아들여놓은 후 다음 작업을 정할 때 최소 처리 시간 작업을 골라야하므로, 중간 중간 작업을 최소 힙에 넣어놓으면 편리하겠다는 생각을 했다.

  다만, 시간을 1ms단위로 반복문 돌리면서 힙을 채우는 풀이를 구상하였고, answer를 구하는 로직을, 모든 작업의 처리 시간을 미리 더해놓고, 시작 시간과 새 작업 처리 시작 시간을 활용해 그 사잇값 만큼만을 따로 더하는 식으로 구상했는데 만점을 받지는 못하였다.

  결국 다른 사람 풀이를 참고해서 풀었다.