배터리가 음수가 되지 않게 만드는 최소 스킵 수
자바스크립트 코딩테스트 문제로 prefix-feasibility 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
배터리 변화 이벤트를 순서대로 겪을 때, 중간 어느 순간에도 배터리가 음수가 되지 않도록 최소 몇 개의 음수 이벤트를 스킵해야 하는지 구하는 문제입니다.
문제 설명
초기 배터리 양 initialBattery와 정수 배열 changes가 주어집니다.
changes[i] > 0이면 그만큼 배터리가 충전됩니다.changes[i] < 0이면 그만큼 배터리가 소모됩니다.changes[i] = 0이면 변화가 없습니다.
이벤트는 왼쪽부터 순서대로 발생합니다. 단, 일부 음수 이벤트는 스킵해서 아예 적용하지 않을 수 있습니다.
이때 이벤트를 처리하는 도중 배터리 양이 한 번도 음수가 되지 않게 만들기 위해 필요한 최소 스킵 횟수를 반환하는 minimumSkipsForNonNegativeBattery 함수를 작성하세요.
양수 이벤트나 0 이벤트는 스킵할 수 없다고 가정합니다.
제한사항
0 <= initialBattery <= 1,000,000,0001 <= changes.length <= 200,000-1,000,000 <= changes[i] <= 1,000,000- 반환값은 스킵한 음수 이벤트의 최소 개수입니다.
- 가능한 한
O(n log n)수준으로 해결해 보세요.
예시
- 입력:
initialBattery = 3,changes = [-4, 2, -3, 1, -2]→ 출력:1 - 입력:
initialBattery = 2,changes = [-3, -4, 5, -2]→ 출력:2 - 입력:
initialBattery = 1,changes = [1, -1, 2, -2, 1]→ 출력:0 - 입력:
initialBattery = 0,changes = [-1, -2, -3]→ 출력:3
힌트
- 일단 이벤트를 모두 적용한다고 생각하고 누적 배터리를 관리해 보세요.
- 음수 이벤트만 따로 기억해 두면, 배터리가 음수가 되는 순간 어떤 이벤트를 취소하는 게 가장 이득인지 판단할 수 있습니다.
- 한 번 스킵해야 한다면, 지금까지 본 음수 중 가장 감소 폭이 큰 이벤트를 빼는 것이 가장 유리합니다.
해설
핵심은 배터리가 음수가 되는 순간마다 지금까지 본 음수 이벤트 중 가장 치명적인 것 하나를 취소하는 전략이 최적이라는 점입니다.
이벤트를 왼쪽부터 그대로 더해 가며 현재 배터리를 current라고 합시다.
또 음수 이벤트를 만날 때마다 그 값을 최소 힙에 넣어 둡니다.
어느 시점에 current < 0 이 되었다면, 지금까지 적용한 음수들 중 적어도 하나는 스킵해야 합니다.
이때 가장 좋은 선택은 가장 작은 값(가장 많이 깎은 음수) 을 스킵하는 것입니다.
예를 들어 지금까지 본 음수가 -2, -7, -3 이라면
하나를 취소할 때 배터리를 가장 많이 회복시키는 선택은 -7을 없애는 것입니다.
다른 음수를 지우는 것보다 항상 손해가 없으므로 greedy가 성립합니다.
진행 방법은 아래와 같습니다.
current를initialBattery로 시작합니다.- 각 이벤트를 순서대로
current에 더합니다. - 음수 이벤트라면 힙에 넣습니다.
- 만약
current < 0이 되면, 힙에서 가장 작은 값 하나를 꺼내 스킵합니다.- 꺼낸 값이 예를 들어
-7이면, 이미 더해졌던-7을 취소하는 것이므로current -= (-7)즉current += 7을 합니다. - 스킵 횟수를 1 증가시킵니다.
- 꺼낸 값이 예를 들어
- 끝까지 처리한 뒤 스킵 횟수를 반환합니다.
이 방법이 맞는 이유는, 어떤 시점에서 배터리를 살리기 위해 하나를 취소해야 한다면 가장 큰 손실을 만든 음수를 제거하는 것이 항상 가장 많은 여유를 남기기 때문입니다. 따라서 이후 시점들까지 생각해도 스킵 횟수를 최소화하는 방향이 됩니다.
각 음수 이벤트는 힙에 한 번 들어가고 많아야 한 번 빠지므로 시간 복잡도는 O(n log n)이고, 추가 공간 복잡도는 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.