LeetCode - Gas Satation

問題の説明

ソースコード

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이 솔루션의 해답이어야만 한다.