[LeetCode] 134. Gas Station (C++)

문제 링크

LeetCode- 134. Gas Station

문제

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.

i번째 위치에서 충전할 수 있는 gas의 양과 i+1번째 위치로 이동하기 위해 필요한 cost 배열이 주어진다.

i번째에서 출발해서 i번째로 돌아오는 것이 가능한 i값을 찾는 문제이다.

해당 경우가 가능하다면 유일하게 1가지 존재하고, 불가능하다면 -1을 반환한다.

풀이

gas와 cost배열의 최대 크기는 10^5이므로 O(N^2)보다 빠른 풀이를 생각해야 했다.

처음 떠올린 방법은 prefix sum을 이용해보면 뭔가 해결할 수 있지 않을까 싶었는데 마땅한 방법이 떠오르지 않았다.

이 문제의 topic이 greedy라는 것을 보고 풀이 방법을 떠올릴 수 있었다.

Key idea

• 먼저 gas[i] - cost[i] 값을 저장한 벡터 V를 하나 생성한다.
  V[i]가 의미하는 바는 i번째에서 이득볼 수 있는 gas의 양이다.

• 이동 방향은 시계방향으로 고정되어 있다. 따라서 V의 가장 끝에서부터 앞으로 오면서 이득볼 수 있는 가스양의 누적합을 확인한다.

• 순환을 마칠 수 있는 가능성이 가장 큰 경우는 i번째에서 시작했을 때 가장 많이 가스를 누적할 수 있는 경우이다.
  ex)

idx         1  2  3  4  5  6  7  8  9  10
gas-cost    0  0  1  1  1 -1 -1 -1 -1  1
sum         0  0  0 -1 -2 -3 -2 -1  0  1

• 만약 gas-cost의 총합이 음수라면 해당 경우는 gas total < cost total 이므로 완주가 불가능하므로 -1을 반환한다.

Code

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int high=-INT_MAX, hidx, sum=0;
        vector<int> V;
        for(int i=0; i<gas.size(); i++){
            V.push_back(gas[i]-cost[i]);
            sum+=V[i];
        }

        if(sum<0) return -1;

        for(int i=V.size()-1; i>=0; i--){
            sum+=V[i];
            if(high<sum){
                high = sum;
                hidx = i;
            }
        }

        return hidx;
    }
};