LeetCode 134 - Gas Station (Medium)

출처: https://leetcode.com/problems/gas-station/

// LeetCode 134 - Gas Station (Medium)
// https://leetcode.com/problems/gas-station/

// 문제 설명
// 원형 경로에 주유소 n개가 있다. i번 주유소의 기름량은 gas[i],
// i번에서 다음 (i+1)번으로 가는 데 드는 비용은 cost[i].
// 빈 탱크로 한 주유소에서 출발해 시계방향으로 원형 경로를 한 바퀴 돌 수 있으면
// 그 출발 인덱스를 반환, 불가능하면 -1. (해가 있으면 유일함이 보장된다.)

// 제약 조건
// n == gas.length == cost.length
// 1 <= n <= 10^5
// 0 <= gas[i], cost[i] <= 10^4
// 답은 유일하도록 입력이 생성됨

// Example 1
// Input : gas = [1,2,3,4,5], cost = [3,4,5,1,2]
// Output: 3
//   3번에서 출발하면 한 바퀴 돌아 돌아올 수 있다.
//
// Example 2
// Input : gas = [2,3,4], cost = [3,4,3]
// Output: -1
//   어디서 출발해도 한 바퀴 불가능.

// 접근 — 그리디 1-pass O(n)
// 핵심은 두 가지 성질이다.
// (1) 전체 gas 합 >= 전체 cost 합 이면 해가 반드시 존재, 아니면 -1.
//     (한 바퀴 순이득 total = sum(gas-cost)가 음수면 절대 못 돈다.)
// (2) start에서 출발해 누적 연료 tank가 i에서 처음 음수가 됐다면,
//     start..i 사이의 어떤 지점에서 출발해도 i를 못 넘는다.
//     → 출발 후보를 i+1로 점프하고 tank를 0으로 리셋.
// total로 해의 존재 여부를, tank로 출발점 후보를 동시에 추적한다.
// 시간 O(n), 공간 O(1).

#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int total = 0;   // 전체 순이득 — 음수면 해 없음
        int tank = 0;    // 현재 출발 후보부터의 누적 연료
        int start = 0;   // 출발점 후보

        for (int i = 0; i < (int)gas.size(); ++i)
        {
            int diff = gas[i] - cost[i];
            total += diff;
            tank += diff;

            if (tank < 0)      // 여기까지 못 옴 → start..i 전부 탈락
            {
                start = i + 1; // 다음 지점을 새 출발 후보로
                tank = 0;      // 누적 리셋
            }
        }
        return total >= 0 ? start : -1;
    }
};