134. Gas Station

Problem

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

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

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

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.

Constraints:

• n == gas.length == cost.length
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

Solution

Problem

• 원형 경로(서킷) 위에 n개의 주유소가 있음.
• 각 주유소 i에서 얻을 수 있는 연료량은 gas[i]이고, 다음 주유소로 이동하는 데 필요한 연료량은 cost[i]임.
• 빈 연료 탱크 상태에서 출발해야 하며, 특정 주유소에서 출발해 한 바퀴를 완주할 수 있는 시작점의 인덱스를 반환해야 함.
• 만약 모든 경우에서 완주가 불가능하면 -1을 반환해야 함.
• 해결 가능한 경우는 유일하다고 보장됨.

Constraints

1. n == gas.length == cost.length

• gas[]와 cost[]의 길이가 동일함.
• 각 주유소는 하나의 gas[i]와 cost[i]를 가짐.

2. 1 ≤ n ≤ 10⁵

• 주유소의 개수가 최대 100,000개 → O(N²) 이상의 알고리즘은 시간 초과 가능성이 있음.
• 반드시 O(N) 이하의 해결 방법을 찾아야 함.

3. 0 ≤ gas[i], cost[i] ≤ 10⁴

• gas[i]와 cost[i]는 0 이상이므로, 연료를 전혀 얻지 못하는 경우도 있을 수 있음.
• 이때, 이동 비용이 더 크면 해당 지점에서는 출발할 수 없음.

4. 문제에서 해결 가능한 경우는 유일하다고 보장됨.

• 유효한 출발점이 있다면 오직 하나만 존재하므로, 여러 개를 탐색할 필요가 없음.

Methodology

1. 브루트포스(완전 탐색) 방식 비효율적

• 각 주유소에서 출발해 모든 경로를 탐색하는 방식.
• O(N²)의 시간 복잡도가 발생할 수 있어 비효율적이므로 사용 불가능.

2. 효율적인 O(N) 해결 방법 (Greedy Algorithm)

• 전체 연료를 계산:
  total_gas = sum(gas)
  total_cost = sum(cost)
  만약 total_gas < total_cost라면, 애초에 출발할 수 없으므로 -1을 반환.

• Greedy 전략을 사용하여 유일한 출발점 찾기:
  current_gas = 0을 초기화하고, start_index = 0으로 설정.
  각 주유소를 순회하면서 current_gas += gas[i] - cost[i]를 업데이트.
  만약 current_gas < 0이 되는 순간, 현재까지의 경로는 실패한 것이므로 다음 주유소부터 새로운 출발점으로 설정.
  마지막으로, 성공적인 출발점은 유일하게 존재하므로 해당 인덱스를 반환.

Time/Spcae Complexity

• 시간 복잡도:

  • total_gas와 total_cost 계산 → O(N)
  • O(N) 한 번의 순회로 출발점 탐색 → O(N)
  • 전체적으로 O(N) + O(N) = O(N) 으로 해결 가능.

• 공간 복잡도:

  • 별도의 추가 배열을 사용하지 않고, 몇 개의 정수 변수만 사용하므로 O(1).

Code

#include <iostream>
#include <vector>

using namespace std;

int canTravelAroundCircuit(vector<int>& gas, vector<int>& cost) {
    int total_gas = 0, total_cost = 0;
    int current_gas = 0, start_index = 0;
    
    int n = gas.size();

    // Step 1: 전체 가스와 비용의 합 계산
    for (int i = 0; i < n; i++) {
        total_gas += gas[i];
        total_cost += cost[i];
    }

    // 전체 가스가 비용보다 적다면 완주 불가능
    if (total_gas < total_cost) {
        return -1;
    }

    // Step 2: Greedy Algorithm으로 출발점 찾기
    for (int i = 0; i < n; i++) {
        current_gas += gas[i] - cost[i];

        // 현재 주유소를 기준으로 더 이상 진행할 수 없는 경우
        if (current_gas < 0) {
            start_index = i + 1;  // 다음 주유소부터 출발
            current_gas = 0;  // 새로운 출발점이므로 초기화
        }
    }

    return start_index;  // 유일한 정답 반환
}

// 테스트 코드
int main() {
    vector<int> gas1 = {1, 2, 3, 4, 5};
    vector<int> cost1 = {3, 4, 5, 1, 2};
    cout << "Output: " << canTravelAroundCircuit(gas1, cost1) << endl;  // Expected: 3

    vector<int> gas2 = {2, 3, 4};
    vector<int> cost2 = {3, 4, 3};
    cout << "Output: " << canTravelAroundCircuit(gas2, cost2) << endl;  // Expected: -1

    return 0;
}