[우선순위 큐] 프로그래머스 level3 디스크 컨트롤러 자바 풀이

프로그래머스 디스크 컨트롤러 자바(java) 풀이

• Level 3
• 해시(Hash)
• 디스크 컨트롤러
  
  
  

문제 정리

1. 하드 디스크는 한 번에 하나의 작업만 수행한다.
2. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 적게하여라.
3. jobs의 길이는 최대 500이다.
4. jobs의 각 행은 [작업이 요청되는 시점, 작업의 소요시간]이다.
5. 각 작업에 대해 소요시간은 최대 1000이다.
6. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

문제 접근

만약 라면공장 문제를 풀지 않고 이 문제를 풀었다면 오래걸렸을 것 같습니다.
하지만 라면공장 문제를 풀고 감을 익혀서 문제를 풀 수 있었습니다.
이 문제는 문제를 파악하고 걸린시간의 평균을 가장 적게 하는 방법만 생각한다면 쉽습니다.

1. 이 문제에 요청시간순으로 입력을 주어진다는 이야기가 없으므로 정렬을 해야합니다. 우선순위 큐에 넣으면서 정렬합니다. (요청시간순 오름차순, 요청시간이 같은 경우 작업 소요시간 오름차순)
2. 어떻게 하면 종료까지 걸린 시간의 평균이 가장 적을까??
   예제를 보고 보류중인 작업이 있을 경우 금방 끝낼 수 있는 작업부터 먼저 끝내게 하면 될것 같다고 생각하였습니다.
   요청시간이 제일 빠른 것부터 차근차근 해나갑니다. 하지만 작업을 수행하는 동안 보류된 작업이 있다면 그 작업들 중에서 작업의 소요시간이 작은 것부터 수행합니다.
   위 두가지를 파악했다면 코드를 짜기위한 준비가 끝났습니다.
   
   
   

문제 풀이

1. 주어진 입력의 정렬을 우선순위 큐를 이용해 정렬합니다. Info 배열에 Comparable을 상속받아 compareTo 함수를 작성하여 위에서 말한대로 정렬을 합니다.
2. ans는 작업 요청부터 종료까지 걸린시간들의 합을 담습니다. end는 이전 작업이 끝난시간을 나타냅니다. 처음에는 수행한 작업이 없으므로 0입니다. pq2는 보류된 작업을 담는 우선순위 큐로 작업 소요시간이 작은 것 부터 수행하기 위해 작업 수행시간 기준 오름차순 정렬합니다.
3. 이전 작업이 끝난 시간과 요청 시간을 비교하여 보류된 작업을 찾습니다. 예를 들어 이전 작업이 3초에 끝났다면 요청시간이 2,3초 인 작업들이 pq2에 들어가게 됩니다.
4. 보류된 작업이 있는 경우 pq2에서 하나꺼내서 수행합니다. 이때 끝날때까지 걸린 시간은 보류된 시간 + 작업 소요시간 입니다. 보류된 시간은 (이전 끝난시간 - 요청 시간)으로 구할 수 있습니다.
   끝난 시간은 이전 끝난시간에 작업의 소요시간을 더해주면 됩니다.
   예를들어 end=3이고 현재 수행한 작업의 요청시간이 2, 작업 소요시간이 6인 경우, 끝난 시간= 3 + 6, 걸린시간 = (3-2) + 6이 됩니다.
5. 만약 보류된 작업이 없는 경우 pq에서 다음으로 할 수 있는 작업을 수행합니다. (문제정리 6번)
   이 경우 걸린시간은 보류되지 않았으므로 작업 소요시간 만큼 걸려서 끝났습니다.
   끝난 시간은 요청시간 + 작업 소요시간이 됩니다.
6. pq와 pq2가 모두 빌때까지 이를 반복합니다. 그리고 구해진 총 소요시간에 job의 개수로 나눠주고 반환합니다.
   
   
   

프로그래머스 디스크 컨트롤러 자바 코드