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;
}
}