134. Gas Station

문제

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

코드

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

        if len(gas) == 1:
            if gas[0]-cost[0] < 0:
                return -1
            else:
                return 0

        left_gas = [0 for _ in range(len(gas))]
        presum = [0 for _ in range(len(gas)+1)]

        tot = 0
        for i in range(len(gas)):
            left_gas[i] = gas[i]-cost[i]
            tot += left_gas[i]

        if tot < 0:
            return -1

        for i in range(len(left_gas)):
            presum[i+1] = presum[i] + left_gas[i]


        min_val = 0
        min_idx = 0

        for i in range(len(presum)):
            if min_val > presum[i]:
                min_val = presum[i]
                min_idx = i

        return min_idx

피드백

• 힘든 취준와중에 자존감 충전용으로 포스팅한다.
• 알고리즘은 다음과 같다.
  • 다음 주유소로 가면서 얻는 기름, 부족한 기름양은 gas[i] - cost[i]다.
  • 모두 합해서 음수가 나오면 한 바퀴 돌 수 가 없다.
  • 이것들을 구간합한다.
  • 대충 다음과 같은 그래프를 얻게된다.
    

    

  • 가장 작은 값을 가지는 항목의 인덱스가 답이다.
• 가장 작은 값을 가지는 항목이 답인 이유는 다음과 같다.
  • 빨간 줄처럼, 즉 y=0에 평행하게 여러 개의 줄을 그어보자.
  • 그리고 그 줄에 교차하는 그래프의 점을 출발점이라고 생각하자.
  • 그러면, 그래프가 음수가 되면 더 이상 여행을 할 수 없게 된다. 기름이 없으니까.
  • 결국 계속해서 기름이 있으려면, 가장 작은 값에서 부터 출발해야 기름이 0 이상을 가지고 그러면 계속해서 순환할 수 있는것이다.
  • 따라서 가장 작은 값을 가지는 항목의 idx가 답이 된다.