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

코딩테스트 - 힙(Heap) - 디스크 컨트롤러 [Level3]

문제링크 : 디스크 컨트롤러

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

문제풀이

Heap 문제입니다.

그런데 저는 힙 없이 사용했습니다.

 일단 가장 먼저 핵심적인 것은

"할 수 있는 작업에서 시간이 짧은 거부터 시작한다"라는 점입니다.

긴 작업 소요시간이 걸리면 그만큼 시간이 남은 작업만큼 배로 더해지기 때문입니다.

 

처음에 jobs를 "작업이 요청되는 시점, 작업의 소요시간" 순으로 정렬합니다. (정렬이 안되어 있음!!)

jobs의 처음 값을 시작으로 

start, end [현재 시간] 그리고 걸린 작업 시간의 합인 count를 지정해줍니다.

 

이제 순회를 돌 때마다

jobs에서 처리 가능한 job을 판단해서

( 작업이 요청되는 시점 < end )

 

tmp_jobs[가능한 작업들이 순서에 맞게 저장되는 곳]에 넣습니다.

(jobs에서 요소를 pop을 하면서 비워질 때까지 합니다.)

 

tmp_jobs에서는 작업 소요시간이 적은 거부터 순서에 맞게 처리를 해야 하므로

매번 순회를 돌 때마다 정렬을 해줍니다.

 

근데 이제 jobs에서 처리 가능한 job이 없다면??

(tmp_jobs 가 비어있다면??)

처리가능한 작업을 만날 때까지 end를 +1 합니다.

 

작업을 처리 할때 마다

end에 작업소요시간을  더해주며

 end에서 작업이 요청되는 시점을 뺀 값을 count에 더해주면 됩니다.

 

결국 tmp_jobs와 jobs가 다 비워지면 count를 디스크 개수로 나누어 출력합니다.

 

 

[Python] 디스크 컨트롤러

 

가장 인기 많은 답변

Most Liked Code

• 힙큐를 사용한 정석 방식이라고 볼 수 있습니다.
  • 확실히 더 간편해 보입니다. 근데 저는 힙큐 쓰는것에 익숙치 않아서;; ㅠ
• max( current_time+ dur, arr + dur ) 을 통해서 작업이 없는 시간을 건너뜁니다.
  • 저는 end를  +1하면서 지나갔는데 시간이 많이 단축될 거 같습니다.
  • 실제로 위 코드가 시간이 조금 더 적게 걸렸습니다.
• 지금보니 제 코드에서 초기값 설정은 전혀 할 필요가 없어보이네요 ㅎㅎ