[LeetCode] Gas Station

문제

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

• If there exists a solution, it is guaranteed to be unique.
• Both input arrays are non-empty and have the same length.
• Each element in the input arrays is a non-negative integer.

Example 1:

Input: gas = [1,2,3,4,5] cost = [3,4,5,1,2] Output: 3 Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4] cost = [3,4,3] Output: -1 Explanation: You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 3 + 2 = 3 Travel to station 1. Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can't travel around the circuit once no matter where you start.

 

Approach

Brute force로 일단 무난하게 통과

0번에서 출발했을때 부터 n-1번에서 부터 출발했을 때 까지 다 해본다

시간복잡도는 O(n^2) (코드 생략)

 

Optimization

문제를 봤을 때 부터 gas[i]에서 cost[i]를 뺀 값을 잘 이용하면 O(n)만에 될 것 같았는데

역시 그러했다.

우선 gas[i] - cost[i]의 총합과 현재 출발점에서 부터의 gas[i] - cost[i]를 기록하는 두 변수와(sum, currSum),

가능한 출발지를 기록하는 변수를 마련한다.

당연히 gas[i] - cost[i]가 0보다 작으면 일주 할 수 없다는 결론이 나온다.

그리고 0번 index에서 출발하여 두 변수를 각각 기록한다.

gas[i] - cost[i]를 currSum에 더했을 때 0보다 크면 다음 인덱스로 진행 가능,

0보다 작으면 더 이상 갈 수 없으므로 출발지를 i+1로 변경하며 currSum을 0으로 다시 초기화 한다.

currSum의 역할은 출발지 ~ i번째 주유소 까지의 gas[i] - cost[i]를 기록하는 것이기 때문에

출발지 ~ i번째 주유소 구간까지의 sum 변수의 역할 또한 병행하는 것이다.

즉, 이게 0보다 작아지면 이 구간 내의 주유소에서 출발했을 때는 가망이 없다는 것을 의미한다.

이러한 특성을 활용해 0~n-1까지 배열을 순방하고

최종적으로 sum이 0보다 작으면 -1, 아니면 기록한 출발지를 return 한다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_GasStation.cpp

chi3236/algorithm