파이썬 알고리즘 인터뷰 81. 주유소

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

 

전체 코드

처음 시도 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        delta_list = []
        start_idx_set = set()
        for i in range(len(gas)):
            delta = gas[i] - cost[i]
            delta_list.append(delta)
            if delta >= 0:
                start_idx_set.add(i)

        start_idx = -1
        while start_idx_set:
            start_idx = start_idx_set.pop()
            i = start_idx
            count = 0
            cur = 0
            length = len(delta_list)
            while count < length:
                if i in start_idx_set:
                    start_idx_set.remove(i)
                i = i % length
                cur += delta_list[i]
                if cur < 0:
                    start_idx = -1
                    break

                i += 1
                count += 1

        if len(start_idx_set) > 0:
            return -1
        return start_idx

예제 코드

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

분석

모듈러 연산을 통해 원형 순환을 해야할거라고 생각했는데 예제 코드에서는 한번 순회하는 것으로 간단히 구현하였다. 이 것이 가능한 이유는 출발점이 존재할 경우 단 1개 존재한다고 문제에 명시되어 있기 때문이다.

출발점이 없는 경우는 sum(gas) < sum(cost)인 경우이므로 이를 -1로 반환하여 예외처리한다. 다음 데이터를 예시로 설명해보자

i=0일 때 gas[i] + fuel < cost[i]이므로 start=i+1, fuel=0으로 초기화된다. start=i+1을 하는 이유는 i=0는 시작할 수 없는 경로이기 때문이다. 이후 i=1~2 역시 동일하게 진행된다.

i=3인 경우엔 gas[i] + fuel > cost[i] 이므로 fuel에 gas[i] - cost[i]만큼 값을 추가한다. i=4도 동일하게 진행한다.

루프 순회가 끝나면 start(=3)을 반환한다. 논리적으로 sum(gas) > sum(cost)이기 때문에 출발점이 존재하고 start 이전에 인덱스는 이동할 수 없는 상태로 끝나기 때문에 단 하나 존재하는 출발점은 start=3이다.