(Leet Code JS)Gas Station

134. Gas Station

 

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:

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

 

주어진 gas와 cost의 각 원소를 같은 인덱스끼리 더해 그 결과를 remainingGas라는 배열에 저장한다.

각 결과가 음수, 0, 양수로 나오기 때문에 음수는 음수끼리 값을 더해주고, 양수는 양수끼리 값을 더해준다.

또한, 덧셈 결과가 양수인 경우 startIndex라는 배열에 해당 인덱스를 넣어준다.

 

만약 remainingGas의 모든 음수 값과 모든 양수 값의 합이 음수가 나오게 된다면 정답에 만족하지 않기 때문에 -1을 리턴해 가지 치기를 해준다.

 

양수라면 탐색 진행.

탐색은 위에서 startIndex에 저장된 인덱스 값에서 탐색을 진행한다.

checkCircuit 함수에 매개 변수로 현재 startIndex[i], remainingGas 배열, gas의 length를 넘겨 주도록 한다.

 

checkCircuit 함수.

들어온 startIndex[i]는 goal로 변수를 저장한다.

goingIndex는 순회할 다음 위치를 나타내기 때문에 goal + 1로 저장.

currentGas는 순회를 하면서 현재 남아있는 가스의 양이다.

이 currentGas가 음수가 나오면 더 이상 진행할 수 없기 때문에 바로 false를 리턴하면 된다.

 

while문으로 goingIndex와 goal이 같을 때까지 반복.

currentGas에 remainingGas[goinIndex++]의 값을 더해준다.

만약 여기서 currentGas가 음수가 나온다면 false.

또한, goingIndex가 gas의 length를 벗어나지 않도록 length와 같아진다면 goingIndex = 0으로 바꿔 순환하게 하면 된다.

 

const checkCircuit = (goal, remainingGas, length) => {
    let goingIndex = goal + 1;
    let currentGas = remainingGas[goal];
    
    if(goingIndex === length){
        goingIndex = 0;
    }
    
    while(goingIndex !== goal){
        currentGas += remainingGas[goingIndex++];
        
        if(currentGas < 0){
            return false;
        }
        
        if(goingIndex === length){
            goingIndex = 0;
        }
    }
    
    return true;
}

const canCompleteCircuit = (gas, cost) => {
    const length = gas.length;
    const remainingGas = Array(length + 1).fill(0);
    const startIndex = [];
    let minusGas = 0;
    let plusGas = 0;
    
    
    for(let i = 0; i < length; i++){
        remainingGas[i] = gas[i] - cost[i];
        
        if(remainingGas[i] >= 0){
            startIndex.push(i);
            plusGas += remainingGas[i];
        } else{
            minusGas += remainingGas[i];
        }
    }
    
    if(plusGas + minusGas < 0){
        return -1;
    }
    
    for(let i = 0; i < startIndex.length; i++){
        if(checkCircuit(startIndex[i], remainingGas, length)){
            return startIndex[i];
        }
    }
    
    return -1;
};