냉각 시간을 지키며 얻는 최대 광고 수익

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

today hard weighted-interval-dp 함수명: maxAdRevenueWithCooldownSlots 제한 시간: 250ms

광고 슬롯 사이에 필요한 냉각 시간을 지키면서 얻을 수 있는 최대 총수익을 구하는 문제입니다.

문제 설명

광고 집행 요청 목록 ads가 주어집니다. 각 광고는 [start, end, revenue] 형태로 주어지며,

start: 광고 시작 시각
end: 광고 종료 시각
revenue: 이 광고를 집행했을 때 얻는 수익 을 뜻합니다.

같은 장비를 연속으로 쓰기 때문에, 어떤 광고를 끝낸 뒤 다음 광고를 시작하려면 최소 cooldown만큼의 빈 시간이 필요합니다.

즉 광고 A를 선택한 뒤 광고 B를 이어서 선택하려면 다음 조건을 만족해야 합니다.

A.end + cooldown <= B.start

서로 겹치지 않는 광고 일부를 골라 얻을 수 있는 최대 총수익을 반환하는 maxAdRevenueWithCooldownSlots 함수를 작성하세요.

제한사항

1 <= ads.length <= 200,000
0 <= start < end <= 1,000,000,000
0 <= revenue <= 1,000,000
0 <= cooldown <= 1,000,000,000
광고는 정렬되어 있지 않을 수 있습니다.

예시

입력: ads = [[1, 3, 50], [4, 6, 60], [7, 9, 70]], cooldown = 1 → 출력: 180
입력: ads = [[1, 4, 80], [3, 5, 50], [6, 8, 70], [9, 10, 30]], cooldown = 3 → 출력: 110
입력: ads = [[2, 5, 40], [5, 9, 35], [8, 11, 90], [10, 12, 45], [13, 15, 60]], cooldown = 0 → 출력: 190

힌트

광고를 종료 시각 기준으로 정렬하면 “현재 광고를 고를 때 바로 이전에 붙일 수 있는 마지막 광고”를 찾기 쉬워집니다.
각 광고에 대해 “이 광고를 고르지 않는 경우”와 “이 광고를 고르는 경우” 중 큰 값을 DP로 비교해 보세요.
호환 가능한 이전 광고 인덱스는 선형 탐색 대신 이분 탐색으로 찾아야 큰 입력도 통과할 수 있습니다.

해설

이 문제는 weighted interval scheduling에 냉각 시간 조건이 추가된 형태입니다.

핵심은 광고를 종료 시각 오름차순으로 정렬한 뒤, 각 광고 i에 대해 다음 두 선택을 비교하는 것입니다.

i번 광고를 고르지 않는다.
- 답은 dp[i - 1]
i번 광고를 고른다.
- i번 광고와 함께 선택 가능한 마지막 광고 p(i)를 찾고
- 답은 revenue[i] + dp[p(i)]

따라서 점화식은 다음과 같습니다.

dp[i] = Math.max(dp[i - 1], revenue[i] + dp[p(i)])

여기서 중요한 점은 호환 조건입니다. 단순히 previous.end <= current.start가 아니라, 냉각 시간까지 포함해서

previous.end + cooldown <= current.start

을 만족해야 합니다.

정렬된 종료 시각 배열이 있으면 current.start - cooldown 이하인 마지막 종료 시각 위치를 이분 탐색으로 찾을 수 있습니다. 이렇게 하면 각 광고마다 O(log n)에 p(i)를 찾을 수 있고, 전체 시간 복잡도는 정렬 포함 O(n log n)입니다.

예를 들어 [[1, 4, 80], [3, 5, 50], [6, 8, 70], [9, 10, 30]], cooldown = 3이라면:

[1, 4, 80] 뒤에는 시작 시각이 7 이상인 광고만 바로 붙일 수 있습니다.
그래서 [6, 8, 70]은 붙일 수 없고 [9, 10, 30]만 가능합니다.
[3, 5, 50] 뒤에도 시작 시각이 8 이상이어야 하므로 [9, 10, 30]은 붙일 수 있습니다.

그래서 최선은 [1, 4, 80] + [9, 10, 30] = 110입니다.

이 방식은 큰 입력에서도 안정적으로 동작하고, 냉각 시간이 0인 경우에는 일반 weighted interval scheduling과 완전히 같은 형태가 됩니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과