LeetCode Gas Station (JavaScript), Greedy

링크 : 

문제 설명

문제

내용

입력

내용

출력

내용

---

문제 풀이

1. (시간초과) 특정 index를 기준으로 순환이 가능한 구조인지 판단하는 로직을 통해 검사 -> 값이 많아지게되면 시간초과 오류가 발생

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    let answer = -1;

    const calCost = (index) => {
        let tank = gas[index];

        for (let i = index + 1; i < gas.length; i++) {
            if (tank - cost[i - 1] < 0) {
                return -1;
            }
            tank = tank - cost[i - 1] + gas[i];
        }

        for (let i = 0; i <= index; i++) {
            let tmp = 0;
            if (i === 0) {
                tmp = tank - cost[gas.length - 1];
            } else {
                tmp = tank - cost[i - 1];
            }

            if (tmp < 0) {
                return -1;
            }
            tank = tmp + gas[i];
        }

        return index;
    }

    for (let i = 0; i < gas.length; i++) {
        answer = calCost(i);
        if (answer !== -1) {
            return answer;
        }
    }

    return answer;
};

 

2. 로직 개선 (그리디)

• 모든 가스의 합이 모든 이동 비용의 합보다 크거나 같다면, 반드시 완주할 수 있는 시작점이 최소 1개는 존재한다.
• 0부터 검사하다가 중간에 실패하면 그 사이의 값은 전부 불가능한 값이다.
  • A 지점에서 출발 -> B 지점에서 가스가 모자라서 멈춘다면 (tank < 0)
    • A와 B 사이의 어떤 지점에서 출발해도 B를 넘길 수 없다.
    • 따라서, B지점에서 실패한다면 그 다음 후보지인 B + 1로 가서 검사를 시작

e.g)

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

1. 시작점(0번 인덱스)에서 출발:
   • gas[0] - cost[0] = 1 - 3 = -2.
   • 0보다 작기 때문에 탈락
   • 다음 시작점은 1번으로. (currentTank는 0으로 초기화)
2. 1번 인덱스에서 출발:
   • gas[1] - cost[1] = 2 - 4 = -2.
   • 0보다 작기 때문에 탈락
   • 다음 시작점은 2번으로.
3. 3번 인덱스(가스 4, 비용 1)에서 출발:
   • gas[3] - cost[3] = 4 - 1 = 3. (현재 currentTank = 3)
   • 다음 칸: gas[4] - cost[4] = 5 - 2 = 3. (현재 currentTank = 6)
   • 배열 끝까지 검사할 경우 일단 후보자는 3번.
4. 마지막 확인:
   • 총 누적 값인 totalTank가 0 이상인지 확인합니다.
   • 0 이상이면 이전에 찾았던 후보자가 정답
   • 아니라면 -1 

---

Q. index 3번에서 출발했는데 왜 한 바퀴를 다시 안 돌아도 되는지?

• 처음에 언급했던 전체 가스 >= 전체 비용 조건이 만족된다면 최소 하나의 경로가 존재한다라는 조건이 만족한다면,
• 3번에서 출발해서 끝까지 도착했을 때 남은 가스(currentTank)가, 앞에서 모자랐던 가스들을 충분히 채울 수 있다는게 보장이 된다.
• 결국, totalTank가 0보다 크다는 것은 순환이 가능하다는 의미이고 이때 구했던 index를 리턴해주면 된다.

 

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    let index = 0;
    let totalTank = 0;
    let currentTank = 0;

    for (let i = 0; i < gas.length; i++) {
        const diff = gas[i] - cost[i];
        totalTank += diff;
        currentTank += diff;

        if (currentTank < 0) {
            index = i + 1;
            currentTank = 0;
        }
    }

    return totalTank >= 0 ? index : -1;
};

---

결론

그리디 문제이지만 최적화를 통해 시간 복잡도를 줄일 수 있는 방안을 찾아야 함.