[LeetCode] 134. Gas Station

😎풀이

해당 문제의 주요 포인트는 아래와 같다.

1. 획득 가능한 전체 가스량이 이동에 필요한 전체 비용보다 작으면 불가능 (-1 반환)
2. N번째 주유소를 시작점으로 순회 중 가스 잔량이 충전량에 비해 부족한다면 불가능 (다음 시작점을 포인트로 변경)
3. 주유소는 재순회 할 필요가 없음. 이전 포인트까지 오는 길이 가능했다면 굳이 재계산 하지 않아도 다음 주유소에서 오는 과정에서도 막히지 않음

function canCompleteCircuit(gas: number[], cost: number[]): number {
    // 전체 가스량이 전체 비용보다 작으면 순회 불가능
    const totalGas = gas.reduce((sum, curr) => sum + curr, 0);
    const totalCost = cost.reduce((sum, curr) => sum + curr, 0);
    if (totalGas < totalCost) return -1;

    let startIndex = 0;  // 시작 인덱스
    let tank = 0;        // 현재 탱크의 가스량

    // 모든 주유소를 순회
    for (let i = 0; i < gas.length; i++) {
        // 현재 위치에서의 가스 잔량 계산
        // (현재 탱크 + 현재 주유소 가스량 - 다음 주유소까지의 비용)
        tank += gas[i] - cost[i];

        // 가스가 부족하면 (음수가 되면)
        if (tank < 0) {
            // 다음 주유소부터 다시 시작
            startIndex = i + 1;
            // 탱크 리셋
            tank = 0;
        }
    }

    return startIndex;
}