Lv.3greedyheapsorting
마감 전에 끝낼 일 고르기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
일 n개가 있습니다. i번 일은 하루가 걸리고, **deadlines[i]일째 이전(그날 포함)**에 끝내면 보수 profits[i]를 받습니다.
하루에 일 하나만 할 수 있고, 1일째부터 일을 시작합니다. 마감을 넘긴 일은 하지 않습니다.
받을 수 있는 보수 합의 최댓값을 반환하세요.
입출력 예
| deadlines | profits | result |
|---|---|---|
[2, 1, 2, 1, 3] | [100, 19, 27, 25, 15] | 142 |
[1, 1, 1] | [5, 9, 2] | 9 |
[1000000000] | [7] | 7 |
입출력 예 설명
예 1 — 1일째 보수 27(마감 2), 2일째 100(마감 2), 3일째 15(마감 3)를 하면 142입니다.
예 2 — 마감이 모두 1일째라 하나만 할 수 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(deadlines: int[], profits: int[]) → long
제한 사항
-
deadlines.lengthprofits.length -
deadlines[i],profits[i] - 답은 32비트 정수를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| deadlines | profits | 기대 출력 |
|---|---|---|
[2,1,2,1,3] | [100,19,27,25,15] | 142 |
[1,1,1] | [5,9,2] | 9 |
[1000000000] | [7] | 7 |
힌트
힌트
일을 마감이 빠른 순으로 보면서, "지금까지 하기로 한 일들"을 보수 기준 최소 힙에 담으세요.
- 일을 일단 힙에 넣습니다.
- 힙의 크기(하기로 한 일의 수)가 지금 일의 마감보다 커지면, 마감 안에 다 할 수 없다는 뜻이니 보수가 가장 작은 일을 하나 뺍니다.
마지막에 힙에 남은 보수의 합이 답입니다. 마감 순으로 보기 때문에, 크기 k인 집합은 항상 1..k일에 순서대로 배치할 수 있습니다.
마감이 까지라 날짜 배열을 만들 수 없다는 점도 이 방법이 편한 이유입니다.
복잡도 목표
보수가 큰 일부터 "마감 이전의 비어 있는 가장 늦은 날"을 한 칸씩 찾아 내려가는 방식은 이라 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1268 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 8 | 판정만 |
| performance | 60 | 4 | 판정만 |