이번에는 프로그래머스 디스크 컨트롤러 문제를 풀었다.
작업마다 요청 시각과 실행 시간이 다르고, 각 작업의 반환 시간 평균을 가장 작게 만들어야 하는 문제였다. 처음에는 요청 시각을 기준으로 정렬하면 될 것 같았다. 하지만 같은 시각까지 들어온 작업이 여러 개라면 어떤 작업을 먼저 실행할지도 따로 정해야 했다.
두 가지 순서를 나눴다
입력 배열은 요청 시각 기준으로 정렬했다. 이렇게 하면 현재 시각까지 들어온 작업을 순서대로 확인할 수 있다.
실제로 실행할 작업은 실행 시간이 짧은 순서로 꺼내야 해서 최소 힙을 사용했다.
- 입력 배열: 요청 시각 오름차순
- 우선순위 큐: 실행 시간 오름차순
현재 시각까지 요청된 작업을 모두 우선순위 큐에 넣고, 그중 실행 시간이 가장 짧은 작업을 꺼냈다. 작업이 끝난 시각에서 요청 시각을 빼면 반환 시간이 나오고, 모든 반환 시간을 더한 뒤 작업 수로 나눴다.
작업이 없는 시간은 바로 건너뛰었다
우선순위 큐가 비었는데 아직 처리하지 않은 작업이 남아 있는 경우도 있었다. 이때 현재 시각을 1씩 늘리면 요청 시각의 범위가 클수록 반복이 많아진다.
그래서 큐가 비어 있으면 현재 시각을 다음 작업의 요청 시각으로 바로 옮겼다. 이후 다시 현재 시각까지 들어온 작업을 큐에 넣었다.
처음에는 이 부분을 별도 조건으로 처리해야 하나 헷갈렸는데, 큐가 비었다는 것은 지금 실행할 수 있는 작업이 없다는 뜻으로 생각하니 정리가 쉬웠다.
복잡도와 결과
작업을 정렬하는 데 O(n log n)이 필요하고, 각 작업을 우선순위 큐에 넣고 꺼내는 데도 전체 O(n log n)이 필요하다. 공간 복잡도는 작업 목록과 우선순위 큐를 사용하므로 O(n)이다.
제출 결과는 정확성 100점, 실행 시간 3.21ms, 메모리 80.6MB였다.
이번 문제는 요청이 들어오는 순서와 실제로 처리할 순서를 같은 기준으로 생각하면 풀기 어려웠다. 후보가 되는 조건은 요청 시각으로 정하고, 후보 중에서 선택하는 기준은 최소 힙으로 분리하는 것이 핵심이었다.
