원형 경로에 n개의 주유소가 있으며, i번째 주유소는 gas[i] 리터의 연료를 가지고 있습니다.

무한한 탱크 용량을 가진 자동차를 사용하여, i번째 주유소에서 i+1번째 주유소로 이동할 때 cost[i] 리터의 연료를 소모합니다. 하나의 주유소에서 출발하여 탱크가 비어 있는 상태에서 시작합니다.

두 정수 배열 gas와 cost가 주어졌을 때, 원형 경로를 한 바퀴 돌 수 있다면 출발 주유소의 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다. 해가 존재하는 경우, 그것이 유일하다고 보장합니다.

입력: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
출력: 3
설명:
3번 주유소(인덱스 3)에서 출발하여 4리터의 연료를 얻습니다. 탱크에는 0 + 4 = 4리터의 연료가 있습니다
4번 주유소로 이동하면 탱크에는 4 - 1 + 5 = 8리터의 연료가 있습니다
0번 주유소로 이동하면 탱크에는 8 - 2 + 1 = 7리터의 연료가 있습니다
1번 주유소로 이동하면 탱크에는 7 - 3 + 2 = 6리터의 연료가 있습니다
2번 주유소로 이동하면 탱크에는 6 - 4 + 3 = 5리터의 연료가 있습니다
3번 주유소로 이동해야 5리터의 연료를 소비하는데, 정확히 돌아올 수 있는 양입니다.
따라서 3은 출발 인덱스가 될 수 있습니다.

내 접근 방식

gas-cost를 통해 각 주유소의 잔여 연료량을 계산할 수 있습니다. 그리고 인덱스 0부터 시작한다고 가정하고, sum += gas[i] - cost[i]를 통해 i 인덱스에 도달했을 때의 잔여 연료량을 계산합니다. 배열 전체를 순회하면서 sum이 0보다 작다면 어떤 경로도 존재하지 않음을 의미하고, 0 이상이라면 경로가 존재함을 의미합니다.

그렇다면 이 경로는 어떻게 찾을 수 있을까요?

경로는 항상 최소 잔여 연료량의 오른쪽에 위치한다는 것을 관찰할 수 있습니다. 마지막에 sum이 0 이상이기 때문에, 최소 연료량의 오른쪽 위치에서 출발하면 가장 많은 연료를 줄이는 부분을 마지막으로 미룰 수 있기 때문입니다.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int minFuel = std::numeric_limits<int>::max(); // 최소 잔여 연료량을 정수 최대값으로 초기화
        int current = 0; // 현재 잔여 연료량
        int size = gas.size(); // 배열 크기
        int start = 0; // 출발 주유소 인덱스

        for (int i = 0; i < size; i++) {
            current += gas[i] - cost[i]; // 잔여 연료량 업데이트, 주유량에서 소모량을 뺌
            if (current < minFuel) { // 현재 잔여 연료량이 최소 잔여 연료량보다 작을 경우
                minFuel = current; // 최소 잔여 연료량 업데이트
                start = i; // 출발 주유소 인덱스 업데이트
            }
        }

        if (current < 0) return -1; // 총 잔여 연료량이 음수라면 한 바퀴를 돌 수 없으므로 -1 반환
        /*
        유일한 해가 아닌 테스트 케이스가 통과되지 않는 문제가 있어 추가 조건을 적용했습니다.
        만약 순회 후 minFuel이 0 이상이라면 모든 경우가 만족되므로 0을 반환합니다.
        */
        if (minFuel >= 0) return 0; // 최소 잔여 연료량이 0 이상이면 출발 주유소에서 시작해 한 바퀴를 돌 수 있음
        return (start + 1) % size; // 출발 주유소 인덱스 + 1을 배열 크기로 나눈 나머지를 반환하여 한 바퀴를 돌 수 있는 위치 반환
    }
};

for 루프 내에서 sum <= min인 경우는 min이 업데이트되는 이유는 잔여 연료량이 특정 패턴을 가질 수 있기 때문입니다.

분명히 우리는 뒤쪽의 최저점이 필요하므로, 같을 때에도 최저 연료량 업데이트가 필요합니다.