[LeetCode 134] Gas Station - 탐욕법(Greedy)으로 해결하기

[LeetCode] Gas Station - 탐욕법(Greedy)으로 해결하기

📌 문제 설명

LeetCode의 "Gas Station" 문제는 각 주유소에서 얻을 수 있는 연료(gas)와 이동에 필요한 연료(cost)가 주어질 때, 전체 주유소를 한 바퀴 돌 수 있는 출발점을 찾는 문제입니다.

• gas[i]: i번째 주유소에서 얻을 수 있는 연료량
• cost[i]: i번째 주유소에서 다음 주유소로 이동하는 데 필요한 연료량
• 한 바퀴를 돌 수 있다면 출발 가능한 주유소의 인덱스 반환, 불가능하면 -1 반환
• 해결 가능한 경우는 유일함이 보장됨

---

📌 문제 해결 과정

✅ 직관적인 접근 (O(N²) 비효율적 방법)

처음에는 모든 주유소에서 출발을 시도하면서 한 바퀴를 도는 방식을 생각할 수 있습니다.

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0;
  const len = gas.length;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      const current = (i + j) % len;
      total += gas[current] - cost[current];
      if (total < 0) {
        total = -1;
        break;
      }
    }
    if (total >= 0) {
      return i;
    }
  }
  return -1;
}

하지만, 이 방식은 모든 주유소에서 출발을 시도하면서 한 바퀴를 도는지 확인하므로 O(N²) 시간이 걸려 비효율적입니다.

---

📌 최적화된 해결 방법 (탐욕법 - Greedy, O(N))

🚀 핵심 아이디어

1. 총 연료량(sum(gas))이 총 비용량(sum(cost))보다 작으면 절대 불가능 → -1 반환
2. 연료가 부족하면 출발점을 다음 주유소로 변경 (이전 주유소에서는 절대 출발 불가능)
3. 연료가 남아있다면 현재 출발점 유지

📌 코드 (O(N))

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalGas = 0;
  let totalCost = 0;
  let startIndex = 0;
  let currentGas = 0;

  for (let i = 0; i < gas.length; i++) {
    totalGas += gas[i];
    totalCost += cost[i];
    currentGas += gas[i] - cost[i];

    // 연료 부족 시, 출발 지점을 다음 주유소로 변경
    if (currentGas < 0) {
      startIndex = i + 1;
      currentGas = 0; // 새로운 출발점에서 다시 시작
    }
  }

  return totalGas >= totalCost ? startIndex : -1;
}

---

📌 코드 실행 과정 예제

입력:

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

Step-by-step 실행 과정

i gas[i] cost[i] currentGas (남은 연료) startIndex (출발점)

0	1	3	-2	1 (출발점 변경)
1	2	4	-2	2 (출발점 변경)
2	3	5	-2	3 (출발점 변경)
3	4	1	3	3 유지
4	5	2	6	3 유지

✅ 최종 반환값: 3 (index 3에서 출발하면 한 바퀴 가능)

---

📌 시간 복잡도 분석

접근법 시간 복잡도 설명

브루트포스 (O(N²))	O(N²)	모든 주유소에서 출발 시도하면서 한 바퀴 순회
탐욕법 (O(N))	O(N)	한 번의 순회로 출발 가능한 주유소 찾음

✅ 탐욕법을 사용하면 O(N)으로 해결 가능! 🚀

---

📌 최종 정리

• 총 연료량 < 총 비용량이면 절대 불가능 (-1 반환)
• 연료 부족 시 출발 지점을 다음 주유소로 변경 (O(N) 순회 한 번만 수행)
• 탐욕법(Greedy)으로 최적화하여 O(N)에 해결 가능

💡 이제 비슷한 문제를 만나면 "탐욕법(Greedy) 접근"을 우선 고려해 보세요! 🚀