Intuition

먼저 카테고리를 보니 Greedy 라고 한다 (...)
아무래도 이런 느낌의 반복되는 수학적 계산 중 최적화된 방법을 찾아내는 문제들은 Greedy를 사용해야하는 듯 하다.
그렇다면 어떤 것이 Greedy인걸까?

First try

첫번째로는 gas - cost 에서 그 합이 0 보다 커야지 한 바퀴를 돌 수 있다는 사실을 이용해 첫번째로 나오는 양수의 위치에서 시작하는 것으로 했지만...
Test case를 통과하지 못했다.

Kadane's Algorithm

discussion을 보니 kadane's algorithm을 보라고 한다.

GeeksforGeeks - Kadane's Algorithm

The idea of Kadane's algorithm is to traverse over the array from left to right and for each element, find the maximum sum among all subarrays ending at that element. The result will be the maximum of all these values.
But, the main issue is how to calculate maximum sum among all the subarrays ending at an element in O(N) time?
To calculate the maximum sum of subarray ending at current element, say maxEnding, we can use the maximum sum ending at the previous element. So for any element, we have two choices:
Choice 1: Extend the maximum sum subarray ending at the previous element by adding the current element to it. If the maximum subarray sum ending at the previous index is positive, then it is always better to extend the subarray.
Choice 2: Start a new subarray starting from the current element. If the maximum subarray sum ending at the previous index is negative, it is always better to start a new subarray from the current element.
This means that maxEnding at index i = max(maxEnding at index (i - 1) + arr[i], arr[i]) and the maximum value of maxEnding at any index will be our answer.

위의 설명을 읽어보니 왠지 현재 gas의 값이 최대인 방향으로 Greedy algorithm을 하면 Kadane과 같이 maximum subarray의 느낌이 날 것 같다는 생각이 들었다.

근데 그렇게 하면 그냥 모든 경우의 수를 실험하는 것과 같은거 아닌가?

Second Try

다른 힌트를 한번 더 보았다. a에서 b로 갈 수 없다면 a와b사이의 어떠한 곳에서도 b에 도달할 수 없다는 댓글이다.

어떻게 하는거지??

답안...

결국 답안을 보았다...

답은 먼저 앞에 말한듯이 gas - cost를 해서 가능한지 확인한다.
그리고나서 가능하다면 끝까지 도달할 수 있는 시작점을 찾는다. 만약 배열의 끝까지 도달할 수 있다면 그 시작점이 답이다.

이유는 앞서 말한듯 만약 끝에 도달할 수 없고 중간에 멈춘다면 그 사이 지점 어느 한 곳이 답이 될수는 없기 때문이다.

결국 앞에 말한 모든 경우의 수를 실험하는 답과 이 답이 다른 점은 먼저 순회할 수 있는지 체크하는 것에 있다.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int gasSum = 0;
        int costSum = 0; 

        for (int i = 0; i < gas.length; i++) {
            gasSum += gas[i]; 
            costSum += cost[i];
        }

        if (gasSum - costSum < 0) {
            return -1; 
        }

        int fuelLeft = 0; 
        int startingIndex = 0;
        for (int i = 0; i < gas.length; i++) {
            if (fuelLeft == 0) {
                startingIndex = i; 
            }

            fuelLeft += gas[i]; 
            fuelLeft -= cost[i];

            if (fuelLeft < 0) {
                fuelLeft = 0;
            }

        }

        return startingIndex;
    }
}