[Leetcode/파이썬] 134. Gas Station

Gas Station

---

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

 

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

 

Constraints:

• n == gas.length == cost.length
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104
• The input is generated such that the answer is unique.

 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        tank = 0    # 연료탱크
        start = 0   # 출발지점

        # 안되는 조건을 알아보자.
        # gas의 합이 cost의 합보다 적으면 이 문제의 조건은 성립하지 않는다.
        if sum(gas) < sum(cost) :
            return -1

        for i in range(len(gas)) :
            tank += gas[i] - cost[i]    # 연료탱크에 gas만큼 넣고 cost만큼 뺀다
            if tank < 0 :               # 만약 목적지에 도착하기 전에 탱크에 연료가 남아있지 않다면
                tank = 0                # 초기화
                start = i + 1           # 출발지점을 옮긴다.
        
        return start

이 문제 처음에 이해가 되지 않아서 한참동안 공부하고 챗GPT에게 이 문제가 무슨 말인지 물어가면서 풀었다.

답은 간단했다. 출발지점에서 주유를 하고, 이동할 때 마다 현재 위치에서 다음 위치 까지 cost만큼 소모된다. 이를 반복하는 행위이다. 

그럼 이 조건이 되려면 적어도 감소하면 안된다. 따라서 gas 배열의 합과 cost 배열의 합이 최소 같아야 이 문제가 성립한다. 다른 말로는 cost의 합이 gas의 합보다 크면 이 문제는 성립하지 않기 때문에 -1을 리턴한다. 처음에 이 조건을 빼먹어서 실행을 돌렸더니 두 번째 케이스에서 틀렸다고 나와서 수정 후 제출하였다.

그 다음 이 문제를 그대로 구현하면 된다. 만약 음수가 나오게 되면 출발지점을 그 다음 칸으로 옮긴 후 다시 출발시키는 코드이다.