[알고리즘] 주유소

주유소

책 풀이

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 모든 주유소 방문 가능 여부 판별
        if sum(gas) < sum(cost):
            return -1

        start, fuel = 0, 0
        for i in range(len(gas)):
            # 출발점이 안되는 지점 판별
            if gas[i] + fuel < cost[i]:
                start = i + 1
                fuel = 0
            else:
                fuel += (gas[i] - cost[i])
        return start

전체 기름의 양이 전체 비용보다 클 경우 반드시 전체를 방문할수 있는 출발점이 존재한다. 원래는 여러 곳이 될 수 있겠지만 이 문제에는 출발점이 유일하다는 제약이 있으므로, 여기서는 반드시 한 군데만 존재하게 된다. 비용이 더 큰 경우는 초기에 예외처리를 해준다.

이 문제는 한 번 이상은 반드시 성립되지 않는 지점이 존재한다. 그렇지 않다면 정답이 복수개가 되기 때문이다. 성립되지 않는 지점이 있다면 그 앞은 전부 출발점이 될 수 없다.