LeetCode - Gas Station (Javascript)

문제 설명

원형으로 이어진 배열 중, 어떤 지점에서 시작해야 정방향으로 돌았을 때 다시 원점으로 돌아올 수 있는지 반환하는 문제다. gas배열에는 해당 각 i지점에서 충전할 수 있는 기름량, cost배열에는 해당 i지점에서 떠날 때 소비해야 하는 기름량이 담겨있다.

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.

Constraints:

• n == gas.length == cost.length
• 1 <= n <= 105
• 0 <= gas[i], cost[i] <= 104

---

소스 코드 (1차 시도)

배열을 slice해서 위치를 바꿔준 뒤, 반복문을 통해 합산을 하려 했는데 시간 초과가 나버렸다…

function canCompleteCircuit(gas, cost) {
  const totalCosts = [];
  let tempArr = [];
  let sum = 0;
  gas.forEach((el, i) => totalCosts.push(gas[i] - cost[i]));
  for (let i = 0; i < totalCosts.length; i++) {
    if (totalCosts[i] < 0) continue;
    tempArr = [...totalCosts.slice(i), ...totalCosts.slice(0, i)];
    sum = tempArr[0];
    for (let j = 0; j < tempArr.length - 1; j++) {
      sum += tempArr[j + 1];
      if (sum < 0) break;
    }
    if (sum >= 0) return i;
  }
  return -1;
}

---

소스 코드 (2차)

통과가 되긴 하는데.. 여전히 시간 복잡도가 처참하다 ㅜ

function canCompleteCircuit(gas, cost) {
  const leftOvers = [];
  let costSum = 0;
  let startPoint = 0;
  let currentFuel = 0;
  gas.forEach((_, i) => leftOvers.push(gas[i] - cost[i]));
  for (let i = 0; i < leftOvers.length; i++) {
    currentFuel += leftOvers[i];
    if (currentFuel < 0) {
      startPoint = i + 1;
      costSum += currentFuel;
      currentFuel = 0;
    }
  }
  return currentFuel + costSum >= 0 ? startPoint : -1;
}

---

소스 코드 (3차 시도)

만족하지는 않지만.. 그래도 2차 시도보다는 조금 더 시간복잡도를 개선했다.
잔여량 구하기 위해 썼던 forEach문 삭제 → for문에서 그냥 잔여량(gas-cost)을 계산했음

function canCompleteCircuit(gas, cost) {
  let costSum = 0;
  let startPoint = 0;
  let currentFuel = 0;
  let totalSumToCheck = 0;
  if (totalSumToCheck < 0) return -1;
  for (let i = 0; i < gas.length; i++) {
    currentFuel += gas[i] - cost[i];
    if (currentFuel < 0) {
      startPoint = i + 1;
      costSum += currentFuel;
      currentFuel = 0;
    }
  }
  return currentFuel + costSum >= 0 ? startPoint : -1;
}

---

로직 설명

크게 어렵지는 않은 로직이다.
핵심은 현재 잔여 기름으로 이전 거리들을 건너오며 발생한 비용들을 감당할 수 있냐 없냐를 판별하는 것이다.

우선 위와 같은 배열을 예시로 들었을 때, 첫 시작점에서 쓰일 기름(gas-cost를 각각 미리 계산해서 담아둔 상태임)은 1이다. 그리고 현재까지 부족했던 기름량은 0이다. (시작점 0이기 때문에)

또한, 현재 기름량은 음수가 아니기 때문에 startPoint는 0이다(i=0).

하지만 다음 주요소(i=1)에서는 기름량이 -2가 되어버린다. 이전 주유소에서 남았던 기름량과 현재 필요한 기름량을 더해주면 1 + -3 이 되므로 -2 음수가 나온다. 따라서 0~1은 시작점이 절대 될 수 없다.

이러한 이유로 startPoint를 i+1 해주는 것이다. (0~1을 아예 배제시킴).

그리고 여기서 중요한 점은, startPoint가 이동됐다는 것은 아예 현재 기름량도 초기화 되어야 한다는 것이다. 말 그대로 startPoint(시작점)이기 때문이다.

그리고 다음 요소로 넘어와서, 현재 기름량은 1이 되고 현재까지 오면서 부족했던 기름량은 startPoint가 유지되더라도 누적되는 것이기 때문에 이전 값과의 연산을 통해 -2가 된다.

위의 예시에서 또 문제가 발생한다.
현재 기름량은 -1이 되어버리기에 0~3은 또 다시 배제되어야 한다. (startPoint = i+1)

다시 startPoint가 초기화 됐으므로, 현재 기름량도 그대로 3이 들어올 수 있다. 이제 배열 요소의 모든 탐색이 끝났으므로 최종 판별만 하면 된다.

여기서 왜 그동안 “현재까지 부족했던 기름량 (costSum)”을 구해왔는지 알 수 있다.
현재까지 부족했던 기름량(costSum)은 0~3까지 이동한다고 가정했을 때 소요될 총 기름량이다.

따라서 (현재 기름량 + 현재까지 부족했던 기름량)의 값이 0이상이면 현재 위치에서 0~3을 순회해도 기름이 부족해지지 않는다는 뜻이다. 따라서 위의 예시는 startPoint 4를 반환하게 된다.

---