Leetcode - 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.

 

 

Approach

주어진 문제는 시계방향으로 주유소를 돌면서 다시 제자리로 돌아올 수 있는지 확인하는 문제다.

다시 제자리로 돌아오면서 연료 탱크의 값이 한번이라도 음수가 되면 -1 을 리턴하면 된다.

 

이문제의 접근법으로 그리디를 선택했는데 선택한 이유는 다음과 같다.

 

1. 로컬 최적 해가 글로벌 최적 해로 이어짐: 문제의 구조상, 어떤 주유소에서 출발해 연료가 바닥나기 전에 다음 주유소에 도달할 수 있다면, 그 선택은 최적의 로컬 해이다. 이러한 로컬 최적의 선택들이 연속적으로 이어질 때 전체 경로를 완주할 수 있는 글로벌 최적 해를 구성한다.
2. 연료의 누적 및 소비 패턴: 주유소에서 연료를 충전하고 다음 주유소로 이동하는 과정에서 연료의 누적과 소비가 일어난다. 그리디 알고리즘을 사용하면 각 단계에서 연료의 누적량과 소비량을 계산하여 현재 상태에서 가장 좋은 결정(다음 주유소로 이동할 수 있는지 여부)을 즉각적으로 내릴 수 있다.
3. 유일한 해의 존재: 문제에서는 해가 존재한다면 그 해가 유일하다고 명시되어 있다. 그리디 알고리즘을 사용하여 한 번의 순회로 출발 가능한 주유소를 찾아낼 수 있으며, 이는 문제의 조건과 일치한다.
4. 효율성: 모든 주유소를 순회하면서 현재 연료량과 각 주유소에서의 연료 충전량, 그리고 다음 주유소로의 이동 비용을 고려하여 그리디 알고리즘을 적용하면, O(n)의 시간 복잡도로 문제를 해결할 수 있다. 이는 대규모 데이터셋에도 효과적으로 작동하는 효율적인 접근 방식이다.

 

func canCompleteCircuit(gas []int, cost []int) int {
	totalGas, totalCost, start, tank := 0, 0, 0, 0

	for i := 0; i < len(gas); i++ {
		currGas := gas[i]
		currCost := cost[i]

		totalGas += currGas
		totalCost += currCost
		tank += currGas - currCost
		if tank < 0 {
			start = i + 1
			tank = 0
		}
	}

	if totalCost > totalGas {
		return -1
	}

	return start
}

 

마지막에 totalCost 와 totalGas 를 비교하는 부분에 대해서 설명하자면 totalCost 가 totalGas 보다 큰경우 어떠한 주유소에서 시작해도 다시 제자리로 돌아올수 없기 때문에 start 값이 유효하지 않다.

그러므로 -1 을 리턴한다.