가장 덜 기다리게 처리하는 작업 순서

자바스크립트 코딩테스트 문제로 shortest-job-scheduling 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium shortest-job-scheduling 함수명: solution 제한 시간: 300ms

문제 설명

작업 목록 jobs가 주어집니다. 각 작업은 [requestTime, duration] 형태이며, requestTime은 작업이 대기열에 들어오는 시각, duration은 처리에 걸리는 시간입니다.

처리 장치는 한 번에 하나의 작업만 수행할 수 있고, 작업을 시작하면 중간에 멈출 수 없습니다. 현재 시각까지 요청된 작업이 여러 개라면 처리 시간이 가장 짧은 작업을 먼저 처리합니다. 처리 시간이 같다면 요청 시각이 더 빠른 작업을 먼저 처리하고, 그것도 같다면 입력에서 더 앞에 나온 작업을 먼저 처리합니다.

모든 작업에 대해 완료 시각 - 요청 시각을 구했을 때, 그 평균의 소수점 아래를 버린 값을 반환하는 solution 함수를 작성하세요.

제한사항

jobs의 길이는 1 이상 100,000 이하입니다.
각 작업은 [requestTime, duration] 형태입니다.
requestTime은 0 이상 1,000,000,000 이하의 정수입니다.
duration은 1 이상 1,000,000 이하의 정수입니다.
작업 입력 순서는 요청 시각 기준으로 정렬되어 있지 않을 수 있습니다.
반환값은 모든 작업의 평균 완료 시간에서 소수점 아래를 버린 정수입니다.

예시

입력: [[0, 3], [1, 9], [2, 6]] → 출력: 9
입력: [[5, 2], [6, 1], [20, 3]] → 출력: 2
입력: [[0, 5], [0, 2], [0, 2], [3, 1]] → 출력: 4

힌트

먼저 작업을 요청 시각 기준으로 정렬해 보세요.
현재 시각까지 들어온 작업만 최소 힙에 넣으면, 매번 가장 짧은 작업을 빠르게 고를 수 있습니다.
대기 중인 작업이 없다면 현재 시각을 다음 작업의 요청 시각으로 바로 옮기면 됩니다.

해설

이 문제는 모든 작업을 단순히 요청 순서대로 처리하면 대기 시간이 길어질 수 있습니다. 현재 처리 가능한 작업 중에서는 처리 시간이 짧은 작업을 먼저 끝내는 방식이 평균 완료 시간을 줄이는 데 유리합니다.

풀이 흐름은 다음과 같습니다.

각 작업에 원래 입력 인덱스를 붙인 뒤 requestTime 기준으로 정렬합니다.
현재 시각 time과 정렬 배열을 가리키는 포인터 i를 둡니다.
requestTime <= time인 작업들을 모두 최소 힙에 넣습니다.
힙에서 duration이 가장 짧은 작업을 꺼내 처리합니다.
작업을 끝낸 시각에서 요청 시각을 빼 완료 시각 - 요청 시각을 누적합니다.
힙이 비었고 아직 들어오지 않은 작업이 남았다면, time을 다음 작업의 요청 시각으로 건너뜁니다.
모든 작업을 처리한 뒤 누적값을 작업 개수로 나누고 소수점 아래를 버립니다.

최소 힙의 정렬 기준은 duration, requestTime, originalIndex 순서로 두면 문제의 tie-break 조건을 안정적으로 처리할 수 있습니다. 정렬과 힙 연산 때문에 시간 복잡도는 O(n log n), 추가 공간 복잡도는 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과