Gas Station

1. 문제 분석

• gas.length == n

• cost.length == n

• 1 <= n <= 10^5
  -> N⋅Log(N) 이하로 풀이하라.
  -> 오래된 문제들의 경우 상수가 작은 O(n^2)풀이로도 1초 내에 통과하는 경우가 많아, 최근 추세로는 n< 2⋅10^5 나 n<5⋅10^5까지 사용하는 경우도 있다.

• 0 <= gas[i], cost[i] <= 10^4

2. Greedy

1) DP와 재귀와의 차이점

우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 공통점이 있음.

하지만 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, Greedy는 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다.

2) Greedy가 필요한 문제

1. Greedy를 사용해도 항상 최적해를 구할 수 있는 문제일 경우, Greedy는 DP를 사용하는 것보다 수행 시간이 훨신 빠르다.

2. 시간, 공간적 제약으로 최적해를 찾기 너무 어려워 근사해가 필요한 경우

3. Why Greedy?

다음 두 가지 측면에서 Greedy 알고리즘의 정당성이 증명될 경우.

• Greedy Choice Property : 동적 계획법처럼 답의 모든 부분을 고려하지 않고 Greedy하게 선택하더라도 최적해를 구할 수 있다.
• Optimal Substructure : 항상 최적의 선택만을 내려 준체 문제의 최적해를 얻을 수 있다

-> Diff(Cur)을 순회하면서 매순간 최적의 판단을 통해 해를 도출하는게 가능함.

4. Greedy Solution

https://leetcode.com/submissions/detail/707691344/

var canCompleteCircuit = function(gas, cost) {
    let start = 0;
    let cur = 0;
    

    //예외처리. totalGas < totalCost
   if((gas.reduce((a,b) => a+b)) < cost.reduce((a,b) => a+b)) return -1
    
    for(let i = 0; i < gas.length; i++){
        if(cur + gas[i] - cost[i] < 0) {
            start = i+1;
            cur = 0;
        }
        else {
            cur = cur + gas[i] -cost[i]
        }
        // console.log(cur, start)
    }
    // console.log(totalGas, totalCost, start)
    
    

    
    return start;
};


//gas   1  2  3  4  5
//cost  3  4  5  1  2
//cur - 2 -2 -2  3  5

// cur 값이 음수가 될때 시작점을 재설정

5. DP Solution

https://leetcode.com/problems/gas-station/discuss/861099/Java-DP-solution-O(1)-space-and-one-pass-O(n)-time

참고1) https://leetcode.com/problems/maximum-subarray/

참고2) https://leetcode.com/problems/maximum-sum-circular-subarray/

참고3) https://leetcode.com/submissions/detail/702709880/

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        long sum = 0;
        int maxLoc = 0, max = 0, minLoc = 0, min = 0;
        int startMax = 0, endMin = 0, newStartMax = 0; 
        for (int i = 0; i < gas.length; ++i) {
            int diff = gas[i] - cost[i];
            sum += diff;
            // Get max subarray sum
            if (maxLoc + diff < 0) {
                maxLoc = 0;
                newStartMax = -1;
            } else {
                if (newStartMax == -1)
                    newStartMax = i;
                maxLoc += diff;
            }
            if (max < maxLoc) {
                max = maxLoc;
                startMax = newStartMax;
            }
            
            // Get min subarray sum
            minLoc = Math.min(0, minLoc + diff);
            if (min > minLoc) { min = minLoc; endMin = i; }
        }
        if (sum < 0)
            return -1;
        if (sum - min > max)
            return endMin + 1;
        return startMax;
    }
}