[LeetCode] Medium - 134 Gas Station

▶134 - 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

 

▶예제

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.

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.

728x90

▶풀이

시작 idx를 모르기 때문에 idx는 (i + cnt) % len(gas)를 하면 몇부터 시작하든 하든 한 바퀴 돌 수 있다.

 

그리고 gas sum과 cost sum을 각 단계별로 저장해두고 만약에 cost sum이 더 커지면 break 해준다.

그렇지 않으면 cnt를 1 증가시켜 주고, 다음 비교를 해주면 된다.

cnt가 len(gas)가 되었는데도 성공했다면 한 바퀴 도는 데 성공한 것이라서 i를 return 해주면 된다.

 

마지막까지 i를 return 하지 못하면 실패라서 -1을 return 해준다.

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

        while i < len(gas):
            gass = 0
            costs = 0
            cnt = 0

            while cnt < len(gas):
                idx = (i + cnt) % len(gas)
                gass += gas[idx]
                costs += cost[idx]
                if gass < costs:
                    break
                cnt += 1
            
            if cnt == len(gas):
                return i
            else:
                i = i + cnt + 1
        
        return -1

처음에 for문을 써서 i를 0부터 n-1까지 모두 확인을 하니까 중간에 시간초과가 났다.

그래서 해결을 못하고 찾아보니 i를 1씩 증가시키는 것이 아닌 cnt + 1을 증가시켜야 한다고 나왔다.

아직 이유를 제대로 확인하지 못했고, 조금 더 분석해봐야 할 것 같다.