Gas Station

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

Gas Station - LeetCode

 

각 지역으로 이동을 위해 가스를 사용하고 충전하는 경우에 전체 지역을 한 바퀴 가능한지 확인하는 문제이다.

 

전체를 이동 가능한 지역은 하나로 유니크하며, 불가능할 경우 판단하여 -1을 리턴해야한다. 기본적으로 전체 지역을 완주하기 위해선 전체 가스의 총량이 전체 이동 코스트보다 낮아야 한다.

 

그렇기 때문에 0번 지역에서 부터 마지막 지역까지 확인하며 가스가 부족해지지 않는 시작 지점을 찾고, 완주할 전체 가스량이 된다면 이동이 가능하다는 것을 알 수 있다. 이러한 그리디 알고리즘으로 해결한 코드이다.

public class Solution {  
    public int canCompleteCircuit(int[] gas, int[] cost) {  
        int sum = 0;  
        int start = 0;  
        int total = 0;  
        for(int i = 0; i < gas.length; i++){  
            sum += gas[i] - cost[i];  
            if(sum < 0){  
                total += sum;  
                start = i + 1;  
                sum = 0;  
            }  
        }  
  
        total += sum;  
  
        return total >= 0  ? start : -1;  
    }  
  
}