주유소 문제 - 134. Gas Station

n개의 주유소가 원형 경로를 따라 위치해 있으며, i번째 주유소에는 gas[i]만큼의 연료가 있습니다.

당신은 무한한 연료 탱크를 가진 자동차를 가지고 있으며, i번째 주유소에서 다음 (i + 1)번째 주유소로 이동하는 데 cost[i]만큼의 연료가 필요합니다. 당신은 어느 한 주유소에서 빈 탱크로 여행을 시작합니다.

두 개의 정수 배열 gas와 cost가 주어질 때, 시계 방향으로 한 바퀴를 돌 수 있는 출발 주유소의 인덱스를 반환하세요. 한 바퀴를 돌 수 없다면 -1을 반환하세요. 만약 해답이 존재한다면, 그 해답은 유일함이 보장됩니다.

예제 1:

• 입력: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
• 출력: 3
• 설명:
  • 주유소 3번(index 3)에서 시작하여 4 단위의 연료를 채웁니다. 탱크 = 0 + 4 = 4
  • 주유소 4번으로 이동합니다. 탱크 = 4 - 1 + 5 = 8
  • 주유소 0번으로 이동합니다. 탱크 = 8 - 2 + 1 = 7
  • 주유소 1번으로 이동합니다. 탱크 = 7 - 3 + 2 = 6
  • 주유소 2번으로 이동합니다. 탱크 = 6 - 4 + 3 = 5
  • 주유소 3번으로 돌아옵니다. 필요한 연료는 5이며, 남은 연료로 다시 주유소 3번으로 돌아갈 수 있습니다.
  • 따라서, 출발 인덱스는 3입니다.

예제 2:

• 입력: gas = [2,3,4], cost = [3,4,3]
• 출력: -1
• 설명:
  • 주유소 0번이나 1번에서 시작하면, 다음 주유소로 이동할 충분한 연료가 없습니다.
  • 주유소 2번에서 시작하여 4 단위의 연료를 채웁니다. 탱크 = 0 + 4 = 4
  • 주유소 0번으로 이동합니다. 탱크 = 4 - 3 + 2 = 3
  • 주유소 1번으로 이동합니다. 탱크 = 3 - 3 + 3 = 3
  • 다시 주유소 2번으로 돌아갈 수 없습니다. 4 단위의 연료가 필요하지만, 3 단위밖에 없습니다.
  • 따라서, 어떤 주유소에서 출발해도 한 바퀴를 돌 수 없습니다.

제한 사항:

• n == gas.length == cost.length
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104

 

풀이

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start = 0
        tank = 0
        total_tank = 0
        
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            total_tank += gas[i] - cost[i]
            
            # If the tank is negative, it means we cannot start from this or any station before this
            if tank < 0:
                start = i + 1
                tank = 0
        
        # If total_tank is non-negative, the start index is valid
        return start if total_tank >= 0 else -1