23.03.02 파이썬 코딩 퀴즈#179 디스크 컨트롤러(프로그래머스 스쿨)

이번 문제는 디스크 컨트롤러 문제이다. 

친절하게 그림설명이 있다. 좀 더 스크롤을 내려 설명을 보자.

위 예시는 전달받은 작업을 순서대로 처리할 경우의 소요시간이다.

하지만 위 예시처럼 A->C->B 순서로 작업을 바꾸면 평균 9ms 가 소요된다.

이제 각 작업에 대해 [작업이 요청되는 시점, 소요시간]이 담긴 2차원 배열을 전달받아, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지를 return 해야 한다.

 

가장 우선시 확인해야 할 부분은 바로 작업이 완료되는데 소요되는 시간이다.

좀 다른 예를 들어 살펴보자.

[0,3] , [1,6], [2,6] 총 3가지 작업을 배정 받았다.

최초에 작업을 하지 않기 때문에 바로 [0,3] 작업이 시행된다.

그리고 1초에 하나, 2초에 하나 총 두개의 작업이 걸린다.

순서대로 처리하게 되면 2번 작업시간 + 3번 작업의 대기시간만큼 3번은 작업 대기 시간을 가진다.

총 작업시간은 [3, 8, 13] 이며 평균 8ms 가 소요되었다.

반대로 3번 작업을 먼저 처리하게 되면 총 작업시간은 [3, 14, 7] 이며, 평균 8ms 가 소요되었다.

즉 작업완료 시간이 같다면 어떤 순서대로 처리해도 동일한 평균 작업 속도를 가진다.

하지만 문제의 예시처럼 [0,3],[1,9],[2,6] 이라면 작업이 진행중인 경우에 한하여 작업 완료시간이 짧은 순서대로 작업하는것이 유리하다.(작업중이 아닐때는 먼저 들어온 작업이 우선 진행된다)

 

이렇게 예제를 통해 해당 문제를 풀이할 방향을 잡을 수 있었다.

1. 작업이 비어있다면 입려된 작업은 바로 투입된다.

2. 현재 작업중이라면, 대기중인 작업중에 소요시간이 짧은 작업을 하는게 평균 작업 속도를 올리는데 유리하다.

이제 코드를 작성할 시간이다.

먼저 3개의 변수를 추가로 선언하여 주었다.

i 는 while문의 종료 조건을 위해 사용되는 jobs의 index와 같고, now 은 현재 경과된 시간이다. start 는 이전 작업이 투입된 시간이다. 즉 start 보다 크고 now 이하인 시간대인 작업들만 현재 바로 투입이 가능한 작업이 된다.

(반복문 전ㄴ에 jobs를 내림차순 정렬 하였는데, 지금 보니 큰 의미가 없는 코드이다.)

그리고 작업 대기열을 담을 heap 배열을 선언하여 주었다.

 

이제 반복문을 통해서 jobs안에 이전 작업시간과 현재 시간 사이의 존재하는 투입 가능한 작업들을 뽑아 heappush()를 사용하여 heap 에 전달한다. 예제를 통해 찾은 2번째 규칙을 사용하기 위해 전달되는 배열은 [소요시간, 투입시간] 으로 뒤집어서 전달하게 되며, 따라서 heap은 소요시간 기준 내림차순 배열을 가지게 된다.

 

한가지 중요한 사실은 heap에서 요소를 뽑아 작업을 진행할 때, while문이 아닌 if문으로 하나의 heap 요소만 사용한다는 점이다. 왜냐하면 하나의 작업을 시행하게되면 다시 now 값과 start 값이 증가하게 되는데, 이 때, 해당 조건을 만족하는 작업들을 더 찾아서 heap 에 넣어주기 위함이다.

 

그리고 마지막으로 heap이 비어있는 상태로 반복문을 돌았다면, now 값을 1 증가시켜 주어 시간이 경과 되었음을 알려준다.