134. Gas Station

문제

• n개의 주유소가 순환 루트에 있다.
• 주어진 Gas와 Cost를 사용해서 한 바퀴를 돌 수 있는 인덱스를 찾기
• 만약에 없다면 -1 리턴하기.

해결방법

• 계속 여행을 할 수 있는 조건은 gas[i] - cost[i+1]가 0보다 클 때
• 그래서 모든 gas[i] - cost[i+1]를 더한 값이 0 보다 작으면 -1 그렇지 않을 경우에는 한 바퀴를 돌 수 있다.
• 그리고 gas[i] - cost[i+1]의 값과 잔여 연료의 값을 더 했을 때 0 보다 큰 값이 나오면 거기서부터 한 바퀴를 돌 수 있다.

int fuel = 0;
int size = gas.length;
for (int i = 0; i < size; i++){
	fuel += gas[i] - cost[i];
}
        
if (fuel < 0) {
	return - 1;
}

모든 gas[i] - cost[i+1]을 fuel에 더해주고 그 값이 0 보다 작으면 -1 리턴.

 

        int curGas = 0;
        int startPosition = 0;
        
        for (int i = 0; i < size; i++) {
            int curCost = gas[i] - cost[i];
            if (curCost + curGas < 0) {
                startPosition = i + 1;
                curGas = 0;
                
            } else {
                curGas += curCost;
            }
        }
        return startPosition;

매번 새로운 Cost 값 (gas[i] - cost[i])을 구해주는데, cost를 잔여 gas와 더 했을 때 0 보다 크면 계속 축적 아니면 i의 gas station에서 한 바퀴 도는게 불가능해진다. 그래서 스타팅 포지션을 +1 해주고 잔여 연료를 0으로 초기화 시켜준다.