[LeetCode] 134. Gas Station

- Problem

134. Gas Station

- 내 풀이 (오답)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        N = len(gas)
        
        for i in range(N):
            total_gas = 0
            if gas[i] >= cost[i]:
                for j in range(i, N+i):
                    total_gas += gas[j%N] - cost[j%N]
                    if total_gas < 0:
                        break
                else:               
                    return i
        
        return -1

• 시간 복잡도: O(N*N)
• 공간 복잡도: O(1)

- 다른 풀이 (정답)

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

        answer = curr_gas = i = 0
        N = len(gas)

        while i < N:
            curr_gas += gas[i] - cost[i]
            if curr_gas < 0:
                answer = i + 1
                curr_gas = 0
            
            i += 1
        
        return answer

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        answer = total_gas = curr_gas = i = 0
        N = len(gas)

        while i < N:
            total_gas += gas[i] - cost[i]
            curr_gas += gas[i] - cost[i]
            if curr_gas < 0:
                answer = i + 1
                curr_gas = 0
            i += 1
        
        return answer if total_gas >= 0 else -1

- 최종 ver

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        answer = total_gas = curr_gas = 0
        N = len(gas)

        for i in range(N):
            total_gas += gas[i] - cost[i]
            curr_gas += gas[i] - cost[i]
            if curr_gas < 0:
                answer = i + 1
                curr_gas = 0

        return answer if total_gas >= 0 else -1

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

- 결과