Leetcode - 134. Gas Station

문제

n개의 주유소가 있고 주유소에 도착하면 얻는 기름 gas[], 그리고 그 주유소를 떠날때 필요한 비용 cost[]가 주어진다. 주유소를 순환해서 순회한다고할때, 몇번째 index에서 출발하면 모두 순회할수 있는지 찾아라.

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.

해결 brute-force - O(n^2)

gas[i] - cost[i]로 새 배열을 만들고 이용하는것이 핵심. 여기서는 가지치기에 이용.
TLE (34 / 37 test cases passed)

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> run;
        int ssize = gas.size();
        for (int i = 0; i < ssize; i++)
            run.push_back(gas[i] - cost[i]);
        
        for (int i = 0; i < ssize; i++) {
            if (run[i] < 0)
                continue;
            
            int tot = 0;
            int idx = i;
            int cnt = 0;
            while (cnt++ < ssize) {
                tot += run[idx++ % ssize];
                if (tot < 0)
                    break;
            }
            if (tot >= 0)
                return i;
        }
        return -1;
        
    }
};

해결 - O(n)

gas[i] - cost[i]를 i와 i+1을 더했을때, 처음으로 양수가 되는 지점을 찾음.

G C
1 3 -> -2 
2 4 -> -2
3 5 -> -2
4 1 ->  3  <--
5 2 ->  3

해설을 참고했는데, 이 해결방안을 처음부터 떠올리기는 쉽지 않은것같다. 수학적 증명이 필요한거라. 엄청 좋은 문제는 아닌것같다.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int ssize = gas.size();
        int surplus = 0;
        int tot_surplus = 0;
        int idx = 0;
        
        for (int i = 0; i < ssize; i++) {
            surplus += gas[i] - cost[i];
            tot_surplus += gas[i] - cost[i];
            if (surplus < 0) {
                surplus = 0;
                idx = i + 1;
            }
        }
        return (tot_surplus < 0) ? -1 : idx;
        
    }
};