2 minute read

134. Gas Station

문제 링크

https://leetcode.com/problems/gas-station/description/

문제 설명

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

제한 사항

  • n == gas.length == cost.length
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4

입출력 예 #1

  1. Input : gas = [1,2,3,4,5], cost = [3,4,5,1,2]
  2. Output : 3
  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.

입출력 예 #2

  1. Input : gas = [2,3,4], cost = [3,4,3]
  2. Output : -1
  3. 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.

문제 풀이

  1. 이중 for문을 통해 주유소 끝까지 순회가능한 인덱스를 찾는다. (시간초과)
  2. 비용의 합이 가스의 합보다 클 경우 어떤 인덱스를 시작점으로 잡아도 전체를 순회할 수 없기에 -1 예외처리, 또한 해당 문제는 한 가지의 경우의 수만 있기에 주유소들 중 중단점이 1개가 있는 것을 이용 중단점 바로 다음 인덱스가 정답인 점을 찾아 풀이한다.
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for start in range(len(gas)):
            fuel = 0
            for i in range(start, len(gas) + start):
                index = i % len(gas)

                can_travel = True
                if gas[index] + fuel < cost[index]:
                    can_travel = False
                    break
                else :
                    fuel += gas[index] - cost[index]
            if can_travel:
                return start
        return -1

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 모든 주유소 방문 가능 여부 판별
        if sum(gas) < sum(cost):
            return -1

        start, fuel = 0, 0
        for i in range(len(gas)):
            # 출발점이 안 되는 지점 판별
            if gas[i] + fuel < cost[i]:
                start = i + 1
                fuel = 0
            else : 
                fuel += gas[i] - cost[i]
            
        return start

Comments

You May Also Enjoy