Problem

---

https://leetcode.com/problems/gas-station/description/?envType=problem-list-v2&envId=greedy

유명한 그리디 유형이지만 그리디인지 파악하기 어려웠던 문제 (Medium)

문제 핵심 요약

상황: 원형 경로에 여러 가스 스테이션이 있고, 각 스테이션의 가스 양(gas)과 다음 스테이션으로 가기 위한 비용(cost)이 주어집니다.

목표

모든 스테이션을 한 바퀴 돌아 제자리로 돌아올 수 있는 시작점의 인덱스를 찾는 것입니다. (답이 존재한다면 유일함)

Solution

---

Brute Force

• 모든 시작점을 검사한다.
  • 시작점(i)부터 총 n개의 역을 방문한다.
    • 원형이므로 인덱스는 (i+j) % n 로 계산해야 한다.
  • 선택한 시작점에서 이동 중 한 지점에서라도 (현재 가스 + 충전량) < 이동 비용이 되면 내부 루프를 탈출하고 다음 시작점(i+1)으로 넘어간다.

Index 0 시작: 가스 1 충전, 비용 2 발생 → 연료 -1 (실패!)
Index 1 시작: 1. 가스 2 충전, 비용 1 발생 → 남은 연료 1
2. 다음(Index 2) 가스 3 충전, 비용 2 발생 → 남은 연료 2
3. 다음(Index 0) 가스 1 충전, 비용 2 발생 → 남은 연료 1 (성공! 시작점 1 반환)

Greedy

• 실패하면 과감히 버린다.
  • 특정 역에 도착했을 때 현재 연료가 마이너스면 이전의 시작점들은 그 역을 통과할 수 없으므로 시작점이 될 수 없다.
  • 다음 역(i+1)을 시작점 후보로 정하고 현재 연료를 0으로 리셋해버린다.
  • 반복문 1바퀴를 돌았을 때 총 연료의 합이 0보다 크면 정답인 시작점이 존재한다는 뜻이므로 시작점을 반환하고 총 연료의 합이 마이너스라면 -1을 반환한다.

각 지점의 차이를 diff 배열이라고 하고 테스트 케이스 하나를 시뮬레이션한다면 아래와 같은 결과가 나온다.

• 입력 데이터: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
• 각 지점의 차이 (diff): [-2, -2, -2, 3, 3]

변수의 의미

• total: 전체 연료량의 합
  • 이 경로가 이론적으로 1바퀴 완주가 가능한가?
  • 리셋하지 않고 모든 diff를 더한다.
  • 루프를 1바퀴 돌았을 때 total이 마이너스가 아니라면 답이 존재한다.
  • 루프를 1바퀴 돌았을 때 total이 마이너스라면 어느 시작점도 1바퀴 완주가 불가능하다는 뜻이므로 -1을 반환한다.
• current: 연료가 바닥나면 리셋되는 값
  • 연료량을 누적하되, 현재 누적한 연료량이 0보다 작으면 0으로 리셋한다.
  • 현재 누적한 연료량이 0보다 작으면 다음 칸을 시작점 후보로 지정한다.

단계 (i)	gas[i] - cost[i] (diff)	total (전체 합)	current (현재 누적)	결정 및 결과
초기값	-	0	0	start = 0으로 시작
0	1 - 3 = -2	-2	-2	current < 0 → 리셋! (start=1, current=0)
1	2 - 4 = -2	-4	-2	current < 0 → 리셋! (start=2, current=0)
2	3 - 5 = -2	-6	-2	current < 0 → 리셋! (start=3, current=0)
3	4 - 1 = 3	-3	3	current >= 0 유지 (start=3 유지)
4	5 - 2 = 3	0	6	current >= 0 유지 (start=3 유지)

Code

---

Brute Force

그리디를 이해하기 위해서 먼저 완전탐색으로 문제풀이를 했다. 리트코드에서는 35/40 테스트 케이스밖에 통과하지 못하고 시간 초과가 난다.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean possible = true;

            // 한 바퀴 돌기
            for (int i = 0; i < n; i++) {
                int idx = (start + i) % n;

                tank += gas[idx];
                tank -= cost[idx];

                if (tank < 0) {
                    possible = false;
                    break;
                }
            }

            if (possible) return start;
        }

        return -1;
    }
}

Greedy

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;     // 전체 합 (가능 여부 판단)
        int current = 0;   // 현재 누적 기름
        int start = 0;     // 시작 인덱스

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

            total += diff;
            current += diff;

            // 🔥 핵심: 여기서 그리디 결정
            if (current < 0) {
                start = i + 1;  // 다음 지점부터 다시 시작
                current = 0;    // 리셋
            }
        }

        // 전체적으로도 불가능하면 -1
        return total >= 0 ? start : -1;
    }
}