[Leetcode] 134. Gas Station - JS

https://leetcode.com/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 원형으로 생긴 도로에 n개의 주유소가 있다.
- i번째에 위치한 주유소의 기름의 양은 gas[i]이다.
- 무제한 탱크통을 가진 차로 i번째 주유소에서 다음인 i+1번째 주유소로 이동하는 비용은 cost[i]
- 하지만 여행 시작할 때, 빈 탱크로 하나의 주유소에서 시작한다.
- gas, cost 두 배열이 주어질 때, 시계방향으로 한번 모든 주유소를 들를 수 있으면
  첫번째 주유소 인덱스를 반환하고 그렇지 않으면 -1을 반환하라.
- 만약 해법이 있다면 이것은 유일한 해법이다.

제한조건
--------------------
- n == gas.length == cost.length
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4

 

2. 접근 방법

접근방법
--------------------
1. 모든 주유수 방문 가능한지 아닌지 판단
2. 가능하다면 몇번째 주유소부터 시작 가능한지 판단

1번 조건 판단 방법
주유소 방문 시 누적 tank의 상태값 갱신 -> gas[i] - cost[i] 추가

2번 조건 판단 방법
주유소 방문 시 gas[i] - cost[i] < 0 이면 해당 주유소에서 시작할 수 없으므로
시작 주유소 인덱스를 다음 주유소 위치로 변경한다.

total_surplus: 누적 tank 양
surplus: 각 주유소에서 gas와 cost 차이
start: 시작 주유소 인덱스

주유소 전체의 가스량과 비용을 고려해서 모두 순회했을 때, 가스보다 비용이 더 크다면
어디서 시작하던지간에 모든 주유소를 도달할 수 없다.

각 주유소마다 가스와 비용을 고려하여 탱크양을 계산하는데
이 때, 비용이 더 크면 해당 주유소에서 시작할 수 없으므로
탱크를 초기화하고 주유소 인덱스를 다음 인덱스로 이동한다.

예를 들어 아래와 같다면,

gas = [5,6,2,8,9]
cost = [4,5,5,2,5]

0번째 -> 1번째 주유소 이동 시, tank = 1 이동 가능 ✅
1번째 -> 2번째 주유소 이동 시, tank = 2 이동 가능 ✅
2번째 -> 3번째 주유소 이동 시, tank = -1 이동 불가능 ❌

위와 같이 결과를 확인하고 나면 생각해볼 것이
"0번째에서 시작했을 때, 실패했으니깐 1번째부터 시작해보자"가 아니라...

"2번째 -> 3번째 주유소 이동 시 실패 했으니, 다음은 3번째 주유소부터 시작하자."

위와 같이 시작 인덱스 최적화를 할 수 있다.

 

 

3. 코드

var canCompleteCircuit = function(gas, cost) {
    const n = gas.length;
    let total_surplus = 0; // 가스와 비용 사이의 차이
    let surplus = 0; // tank
    let start = 0; // 주유소 인덱스

    for (let i = 0; i < n; i++) {
        total_surplus += gas[i] - cost[i];
        surplus += gas[i] - cost[i];
        if (surplus < 0) { // tank가 부족하면
            surplus = 0; // 탱크 초기화하고
            start = i + 1; // 주유소 인덱스를 현재 다음 위치로 이동시킨다.
        }
    }
    return (total_surplus < 0) ? -1 : start;
};

모든 주유소의 가스와 비용의 차이가 음수면, 어디서 시작하던지간에 모든 주유소를 순회할 수 없으므로 -1을 반환한다.

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

Brute Force 방법으로 시간 복잡도 O(n^2) 방법으론 풀었지만, 시간초과가 발생하여 고민하다가 해설을 보고 공부했다.

 

2번째 풀이 때도 10분안에 풀지 못하였다.

기억력이 오래 가지 않는 것 같다. 문제가 얼핏 기억이 나긴 하지만 어떻게 접근해야할지 도통 생각이 나질 않았다.

결국 다시 풀이를 보고 공부했다.

 

2번째 공부할 때는 목표를 단순화했다.

 

1. 모든 주유소를 순회가 가능한지?

2. 순회가 가능하다면 몇번째 주유소부터 가능한지?

 

위 조건을 성립하기 위한 조건을 세웠다.

 

1번 조건은 주유소를 순회하면서 전체 탱크의 양을 누적하여 계산했을 때 값이 음수면 순회가 불가능하다는 것을 알 수 있다.

2번 조건은 주유소를 순회하면서 현재 주유소 양과 비용의 차를 계산했을 때, 값이 음수면 현재 주유소에서는 시작이 불가하는 것을 알 수 있다.

 

위 두 조건을 하나의 반복문 순회에서 확인하도록 코드를 작성했다.

 

위와 같이 2가지 조건을 두고 접근하니 이해가 더 쉬웠다.