LeetCode - Gas Satation

문제 설명

순환하는 경로를 따라 n개의 주유소가 있으며 i번째 주유소의 가스량은 가스(gas)[i]를 가진다.
주유를 이론적으로는 무한대로 할 수 있는 자동차가 있고,
i번째 스테이션에서 다음 (i + 1)번째 스테이션까지 이동하는 데에는 가스 비용(cost)[i]이 든다.

이 자동차는 주유소 중 한 곳에서 기름이 0인 상태로 여행을 시작한다.
두 개의 정수 배열 가스와 비용이 주어지면 시계 방향으로 한 번 순환할 수 있다면 시작하는 주유소의 인덱스를 반환하고, 그렇지 않으면 -1을 반환한다. 솔루션이 존재한다면 그 솔루션은 유니크함을 보장한다(솔루션은 1개만 존재한다).

인풋 예시는 다음과 같다.

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1

소스 코드

const canCompleteCircuit = (gas, cost) => {
    // gas의 총량이 cost의 총량보다 크다는 것을 우선 보장한다. 이는 solution이 하나 무조건 존재할 것이라는 뜻을 내포한다. (only ONE Unique solution)
    if(gas.reduce((a,b) => a+b) < cost.reduce((a,b) => a+b)) return -1;

    let total = 0;
    let res = 0;

    for (i = 0; i < gas.length; i++) {
        total += (gas[i] - cost[i]);
        // total < 0 이라면 현재의 인덱스 i는 솔루션이 될 수 없다.
        if(total < 0) {
            // gas의 총량이 cost의 총량보다 크다는 것이 보장되어있으므로 negative의 총합을 굳이 알 필요가 없다. 따라서 total을 0으로 초기화해준다.
            total = 0;
            // 현재의 인덱스 i는 솔루션이 원하는 해당 인덱스가 아니다. 따라서 그 다음 인덱스로 다시 for 문을 돌며 조건을 만족하는지 찾아보자 (그리디스럽게) 
            // 물론 맨 위의 방어조건에 따라 솔루션은 무조건 하나가 보장되어 있을 것이며, 이는 예로 [-2, -2, -2, 3, 3] 이라면 첫번째 3(gas의 인덱스 3)이 무조건 솔루션이 되어야함을 얘기한다.
            res = i + 1;  
        }
    }
    return res;
};
console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]));
// console.log(canCompleteCircuit([2, 3, 4], [3, 4, 3]));


// [-2, -2, -2, 3, 3];
// 여기서 첫번째 3이 솔루션의 해답이어야만 한다.

시간복잡도는 O(n)이다.