[Leetcode/C++] 134_Gas Station

문제는 다음과 같습니다.

이 문제를 두 가지 방법으로 풀었는데,
처음 풀었던 풀이는 시간초과가 난 풀이입니다.
풀이는 다음과 같습니다.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start_idx=-1;
        int n = gas.size(); int cnt=0;
        vector<int> gas_copy = gas; vector<int> cost_copy = cost;
        gas.insert(gas.end(), gas_copy.begin(), gas_copy.end());
        cost.insert(cost.end(), cost_copy.begin(), cost_copy.end());
        
        for(int i=0; i<n; i++){
            if(gas[i]<cost[i]) continue;
            
            int sum = gas[i];
            int j;
            for(j=i; j<i+n; j++){
                if(cost[j]>sum) break;
                sum += (-cost[j] + gas[j+1]);
            }
            if(j==i+n){
                start_idx=i;
                break;
            }
        }
        
        return start_idx;
    }
};

이 방식은
시작점을 찾고 시작점을 기준으로 n만큼 돌기 때문에
총 시간복잡도는 O(n^2)입니다.

O(n)으로 풀어야 시간초과가 안 나는것 같아서
다시 풀었습니다.

풀이는 다음과 같습니다.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start_idx=0;
        int n = gas.size(); int sum=0;
        
        int gas_sum = accumulate(gas.begin(), gas.end(), 0);
        int cost_sum = accumulate(cost.begin(), cost.end(), 0);
        if(cost_sum > gas_sum) return -1;
        
        for(int i=0; i<n; i++){
            sum += gas[i]-cost[i];
            if(sum<0){
                start_idx=i+1;
                sum=0;
            }
        }
        return start_idx;
    }
};

저는 입력받은 gas, cost의 벡터의 총 합을 구해 먼저 비교함으로써,
애초에 "cost의 합이 > gas의 합" 인 경우를 먼저 처리했구요,

이 뒤부터는 시작하는 인덱스만 구하면 되기 때문에,
여행을 하면서 드는 경비인 gas[i]-cost[i]를 sum변수에 누적해서 더한 뒤에,

이 sum이 0 이상이면 계속해서 i값을 갱신해나가고,
sum이 음수이면, 시작인덱스를 i+1로 갱신을 하여 이후의 i부터 누적해서 sum에 더하도록 하였습니다.