LeetCode 134. Gas Station

파이썬 알고리즘 인터뷰 81번(리트코드 134번) Gas Station
https://leetcode.com/problems/gas-station/

나의 풀이

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curr = 0
        min_diff = 0
        min_idx = -1
        for i in range(len(gas)):
            curr += gas[i] - cost[i]
            if curr < min_diff:
                min_diff = curr
                min_idx = i
        if curr < 0:
            return -1
        return 0 if min_idx == len(gas) - 1 else min_idx + 1

• 연료가 음수여도 달릴 수 있다고 하자.
• 출발 후 제자리로 오며 각 지점에서 gas를 더하고 cost를 뺀다.
• 제자리로 왔을 때 누적 합이 음수이면 불가능한 경우이므로 -1을 반환한다.
• 그렇지 않다면, 가장 많은 빚을 진 지점 다음 지점에서 출발하면 된다.

다른 풀이

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if (sum(gas) - sum(cost) < 0):
            return -1
        
        gas_tank, start_index = 0, 0
        
        for i in range(len(gas)):
            gas_tank += gas[i] - cost[i]
            
            if gas_tank < 0:
                start_index = i+1
                gas_tank = 0
            
        return start_index

• 처음에 이 풀이를 보고 갸우뚱했다.
• start_index 지점에서 출발해서 이동하다가 gas_tank가 음수가 되면 그 사이 지점은 모두 무시하고 현재 다음 칸으로 start_index를 업데이트한다. 그 사이에서 출발하는 경우도 될 수 있는데? 싶었는데 문제 조건을 잘 읽어보면, 출발지가 존재한다면 유일하다는 조건이 있었다. 이 조건이 핵심이고 따라서 이런 풀이가 가능하다. 하지만 나는 나의 풀이가 더 마음에 든다.