[우선순위큐] 프로그래머스 디스크 컨트롤러

1. 문제 요약

- 일정 Job을 수행하는 디스크 컨트롤러 1개가 있을 때, Job 정렬을 최적화했을 때 나오는 min(평균 소요 시간) 구해라

 

2. 문제 풀이

문제 풀이는 중심 개념과 전체 구조를 이해하려고 해보려고 함

 

(1) 기본 원리

 ! Job 길이가 제일 짧은 것부터 실행하는 것이 최적화 방법임

 ! Job이 실행될 동안 들어온 Job은 "대기큐" 또는 "실행큐"에 넣어둠(*일종의 Wait)

  *실행큐인 경우는, 작업 실행 동안 새로 들어온 Job 없을 경우 그냥 실행될 Job을 저장한 큐로 취급

 

(2) 전체 구조

  //part1. 필요 자료구조

  - 시작시작 빠른 순으로 정렬 → Jobs('input' 주어짐)

  - 우선순위 큐(min) 선언 → Job 대기용

  - 현재 Job 처리 끝난 시점 → end

 //part2. Job 시작 (*다 수행할때까지)

 //part2-1. Job 대기시키기

  - 현재 실행 Job 끝나기 전에 요청 들어온 Job 대기시키고

  - 대기시킬 Job 없으면 가장 다음 Job을 대기시킴(*part2-2에서 변수 조정 필요)

 //part2-2. Job 대기줄 비었으면 다음 Job 불러오게 세팅

  *Job 대기줄 비었음 → 마지막으로 실행된 Job의 종료시점 = 새로운 end로 업데이트

 //part2-3. Job 대기줄 처리

  - 수행한 Job 수++, 수행시간 합계

  - 현재 Job 처리 끝난 시점(변수 end) 업데이트

 //part3. 평균 대기 시간 계산

  - 총소요시간을 Job 수로 나누기

 

3. 참조

https://codevang.tistory.com/316

프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA)