리트코드 134번 Gas Station (python)

Problem

https://leetcode.com/problems/gas-station/description/

Solution

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return - 1

        start, fuel = 0, 0
        for idx in range(len(gas)):
            if fuel + gas[idx] < cost[idx]:
                start = idx + 1
                fuel = 0
            else:
                fuel += gas[idx] - cost[idx]

        return start

gas의 합보다 cost의 합이 크다면 해가 있을 수 없다.

문제에서 정답이 될 수 있는 케이스는 유일하다 했으므로 해당 값을 찾는다.

Reference

파이썬 알고리즘 인터뷰 81번