만료 전에 가장 많이 쓰는 쿠폰 수
자바스크립트 코딩테스트 문제로 expiring-interval-greedy 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
쿠폰마다 사용할 수 있는 시작일과 만료일이 [start, end] 형태로 주어집니다.
하루에는 쿠폰을 최대 1장만 사용할 수 있고, 어떤 쿠폰은 start <= day <= end인 날에만 사용할 수 있습니다.
가장 많이 사용할 수 있는 쿠폰 수를 구하는 maxUsableExpiringCoupons 함수를 작성하세요.
제한사항
coupons는[start, end]형태의 배열입니다.0 <= coupons.length <= 1000001 <= start <= end <= 1000000000- 하루에는 쿠폰을 최대 1장만 사용할 수 있습니다.
- 쿠폰 입력 순서는 정렬되어 있지 않을 수 있습니다.
- 사용할 수 없는 쿠폰은 버려도 됩니다.
예시
- 입력:
coupons = [[1, 2], [1, 2], [2, 3], [3, 3]]-> 출력:3 - 입력:
coupons = [[5, 5], [1, 10], [2, 3], [2, 3]]-> 출력:4 - 입력:
coupons = [[1, 1], [1, 1], [1, 1]]-> 출력:1 - 입력:
coupons = []-> 출력:0
힌트
- 시작일이 빠른 쿠폰부터 볼 수 있도록 정렬해 보세요.
- 현재 날짜에 사용할 수 있는 쿠폰 중에서는 만료일이 가장 빠른 쿠폰을 먼저 쓰는 것이 유리합니다.
- 아무 쿠폰도 사용할 수 없는 날짜를 하루씩 넘기면 오래 걸릴 수 있으니, 다음 쿠폰의 시작일로 바로 이동하는 방법을 생각해 보세요.
해설
이 문제는 “지금 쓸 수 있는 쿠폰 중 가장 빨리 만료되는 것부터 사용한다”는 그리디 전략으로 풀 수 있습니다.
쿠폰을 시작일 기준으로 정렬해 둔 뒤, 현재 날짜까지 사용할 수 있게 된 쿠폰들의 만료일을 최소 힙에 넣습니다. 그리고 이미 만료된 쿠폰은 힙에서 제거합니다.
힙에 남은 쿠폰이 있다면 그중 만료일이 가장 빠른 쿠폰을 하나 사용합니다. 이 쿠폰을 늦게 쓰면 더 빨리 만료되는 기회를 잃을 수 있으므로, 가장 먼저 처리하는 것이 안전합니다. 쿠폰을 하나 사용했으니 날짜를 하루 뒤로 옮깁니다.
반대로 힙이 비어 있다면 현재 날짜에 사용할 수 있는 쿠폰이 없다는 뜻입니다. 이때는 다음 쿠폰의 시작일로 날짜를 바로 이동하면 불필요한 날짜 순회를 피할 수 있습니다.
풀이 순서는 다음과 같습니다.
coupons를 시작일 오름차순으로 정렬합니다.- 현재 날짜
day, 쿠폰 인덱스i, 사용 개수used를 준비합니다. - 힙이 비어 있고 다음 쿠폰의 시작일이 현재 날짜보다 뒤라면
day를 그 시작일로 옮깁니다. start <= day인 쿠폰들의end를 최소 힙에 넣습니다.end < day인 만료 쿠폰은 힙에서 제거합니다.- 힙에 쿠폰이 남아 있으면 하나를 꺼내 사용하고
used와day를 1씩 늘립니다. - 모든 쿠폰을 확인하고 힙도 비면
used를 반환합니다.
정렬에 O(n log n), 각 쿠폰의 힙 삽입과 삭제에 O(log n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.