한 바퀴 배송을 완주할 수 있는 첫 출발 지점
자바스크립트 코딩테스트 문제로 circular-greedy 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
원형으로 배치된 배송 거점이 있습니다. 각 거점 i에서는 supplies[i]만큼 배터리를 충전할 수 있고, 다음 거점으로 이동하려면 costs[i]만큼 배터리가 필요합니다.
어느 한 거점에서 출발해 거점을 순서대로 이동하며 다시 출발한 곳까지 돌아오려 합니다. 출발 시 배터리는 0이고, 각 거점에 도착하면 먼저 그 거점의 충전량을 얻은 뒤 다음 거점으로 이동할 수 있습니다.
한 바퀴를 끝까지 완주할 수 있는 출발 지점의 인덱스를 반환하세요. 가능한 출발 지점이 없다면 -1을 반환하세요. 가능하다면 가장 이른 인덱스를 반환하면 됩니다.
제한사항
supplies.length === costs.length- 거점 수는
1이상100,000이하입니다. - 각 원소는
0이상1,000,000이하의 정수입니다. - 인덱스는
0부터 시작합니다. - 반환값은 완주 가능한 가장 이른 시작 인덱스, 없으면
-1입니다.
예시
- 입력:
supplies = [4, 6, 7, 4],costs = [6, 5, 3, 5]→ 출력:1 - 입력:
supplies = [2, 3, 4],costs = [3, 4, 3]→ 출력:-1 - 입력:
supplies = [5],costs = [4]→ 출력:0 - 입력:
supplies = [1, 2, 3, 4],costs = [2, 2, 2, 2]→ 출력:1
힌트
- 각 거점에서 실제로 남거나 부족해지는 값은
supplies[i] - costs[i]입니다. - 전체 충전량 합이 전체 소모량 합보다 작다면 시작점을 어떻게 골라도 완주할 수 없습니다.
- 어떤 구간을 지나던 중 누적 배터리가 음수가 되면, 그 구간 안의 어떤 지점도 시작점 후보가 될 수 없는 이유를 생각해 보세요.
해설
이 문제의 핵심은 각 거점에서 얻는 양과 잃는 양의 차이만 보면 된다는 점입니다.
diff = supplies[i] - costs[i]라고 두면, 한 바퀴를 완주할 수 있으려면 전체 diff의 합이 최소 0이어야 합니다. 전체 합이 음수면 어디서 출발해도 결국 배터리가 모자랍니다.
완주 가능성이 있을 때는 왼쪽부터 한 번만 훑으며 시작점을 찾을 수 있습니다.
currentBalance에 현재 후보 시작점부터 지금까지의 누적 차이를 더합니다.- 이 값이 음수가 되면, 현재 후보 시작점부터 지금 위치까지의 어떤 지점에서 출발해도 지금 위치 다음으로 넘어갈 수 없습니다.
- 따라서 시작점 후보를
i + 1로 옮기고,currentBalance를0으로 초기화합니다. - 끝까지 순회한 뒤 전체 합이 0 이상이면 마지막으로 남은 후보가 정답입니다.
예를 들어 supplies = [4, 6, 7, 4], costs = [6, 5, 3, 5]이면 차이는 [-2, 1, 4, -1]입니다.
- 0번에서 시작하면 첫 칸에서 바로 누적 합이
-2가 되어 실패합니다. - 그러면 0번을 포함한 그 구간은 후보에서 제외하고 1번부터 다시 봅니다.
- 1번부터는
1 -> 5 -> 4 -> 2처럼 끝까지 음수가 되지 않으므로 완주 가능합니다.
이 방식은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 공간 복잡도는 O(1)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.