마감 전에 끝낼 수 있는 최대 작업 수
자바스크립트 코딩테스트 문제로 deadline-scheduling 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
작업마다 소요 시간과 마감일이 주어질 때, 제시간 안에 끝낼 수 있는 작업 개수의 최댓값을 구하는 문제입니다.
문제 설명
작업 목록 tasks가 주어집니다.
각 작업은 [duration, deadline] 형태로 표현됩니다.
duration: 그 작업을 끝내는 데 걸리는 시간deadline: 이 시각 이하에 작업이 끝나야 제시간에 완료된 것으로 인정
한 번에 하나의 작업만 할 수 있고, 작업은 중간에 멈췄다가 나중에 이어서 할 수 없습니다. 작업 시작 순서는 직접 정할 수 있습니다.
이때 제시간 안에 끝낼 수 있는 작업 수의 최댓값을 반환하는 maxTasksBeforeDeadlines 함수를 작성하세요.
제한사항
tasks의 길이는0이상100,000이하입니다.- 각 작업의 소요 시간
duration은1이상1,000,000이하입니다. - 각 작업의 마감일
deadline은1이상1,000,000이하입니다. - 모든 작업은 정수로 주어집니다.
- 반환값은 제시간 안에 끝낼 수 있는 작업 개수의 최댓값입니다.
예시
- 입력:
tasks = [[3, 4], [2, 6], [4, 7], [1, 8]]→ 출력:3 - 입력:
tasks = [[5, 5], [4, 6], [2, 6]]→ 출력:2 - 입력:
tasks = [[10, 3], [2, 3], [1, 3]]→ 출력:2
힌트
- 어떤 작업을 먼저 볼지 정렬 기준부터 생각해 보세요.
- 지금까지 고른 작업들의 총 소요 시간이 중요합니다.
- 마감일을 넘긴 순간, 선택한 작업 중 하나를 포기해야 한다면 무엇을 버리는 게 가장 유리할까요?
해설
핵심은 마감일이 빠른 작업부터 고려하는 것입니다.
- 작업을
deadline오름차순으로 정렬합니다. - 작업을 하나씩 보면서 일단 선택했다고 생각하고 총 소요 시간을 더합니다.
- 만약 총 소요 시간이 현재 작업의 마감일보다 커지면, 지금까지 선택한 작업들 중 가장 오래 걸리는 작업 하나를 제거합니다.
왜 가장 긴 작업을 빼야 할까요?
- 작업 수를 최대한 많이 남기려면, 같은 1개를 포기하더라도 시간을 가장 많이 되돌려받는 선택이 유리합니다.
- 그래서 선택된 작업들의
duration을 빠르게 관리하려면 최대 힙이 잘 맞습니다.
예를 들어 [[5, 5], [4, 6], [2, 6]]을 마감일 순서로 보면:
[5, 5]선택 → 총 5[4, 6]선택 → 총 9 (마감 6 초과)- 선택한 작업 중 가장 긴
5를 제거 → 총 4
- 선택한 작업 중 가장 긴
[2, 6]선택 → 총 6
결국 2개 작업을 제시간 안에 끝낼 수 있습니다.
이 방식의 시간 복잡도는 정렬 O(n log n)과 힙 연산 O(n log n)을 합쳐 전체 O(n log n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.