[LeetCode] 134. Gas Station - 탐욕법(그리디, Greedy) JAVA

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

코드설명

탐욕법(그리디, Greedy)을 활용합니다.

 

문제의 핵심은, totalGas 가 totalCost보다 반드시 커야만, 원래의 시작점으로 돌아올 수 있습니다.

또한, 이동처리를 하면서 currentGas가 < 0 이 되는 경우가 발생하는데, 이때는 0~해당 위치까지 모두 CircularRoute가 불가능합니다. (gas와 cost가 누적으로 계산되기 때문입니다.)

그러므로, 0에서부터만 n까지만 처리해도 가능한 것 입니다. (물론, totalGas가 totalCost보다 크다면 반드시 순회가 가능하다는 조건이 있게 그렇습니다.)

코드

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        int currentGas = 0;

        int startIdx = 0;
        for(int i=0; i<gas.length; i++){
            totalGas += gas[i];
            totalCost += cost[i];
            currentGas += gas[i] - cost[i];
            if(currentGas < 0){
                currentGas =0;
                startIdx = i + 1;
            }
        }
        return totalGas >= totalCost ? startIdx : -1;
    }
}

 

시간초과가 발생하는 코드입니다. O(N^2) 이기에 10^10 입니다.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        
        int gasLength = gas.length;
        for(int startStation = 0; startStation < gasLength; startStation++){
            int tank = gas[startStation];
            boolean isTravelBack = true;
            for(int i=startStation; i < startStation + gasLength; i++){
                tank += -cost[i % gasLength]; 
                if(tank < 0){
                    isTravelBack = false;
                    break;
                }
                tank += gas[(i + 1) % gasLength];
            }
            if(isTravelBack == true){
                return startStation;
            }
        }
        return -1;
   }
}