[LeetCode] Gas Station C++ 풀이

https://leetcode.com/problems/gas-station/?envType=problem-list-v2&envId=dglcn6pr

Gas Station - LeetCode

 

Description:

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
• The input is generated such that the answer is unique.

 

브루트 포스로 풀면 O(N^2)의 시간복잡도가 나오는 문제이다. 입력 제한이 커서 Optimization이 필요하다. 

한가지 최적화 방법은 문제의 특징을 사용해서 O(N^2)의 순회를 하되, 중간에 Skipping을 할 수 있다. 

i에서 출발해서 j 에서 연료가 모자라 실패했다면, 다음 순회는 i + 1가 아니라 j + 1에서 시작하면 된다. 

왜냐하면, i와 j 사이에 어디에서 출발하든 연료는 똑같이 모자랄 수 밖에 없기 때문이다. 

예를 들어, 아래와 같은 입력이 주어질 때

index = 0 1 2 3 4 

gas    = 1 2 3 4 5

cost   = 3 4 5 1 2

 

4번째 인덱스에서 출발한다고 하자. 

current = 4: totalGas = 0 + 5 - 2 = 3

current = 0: totalGas = 3 + 1 - 3 = 1

current = 1: totalGas = 1 + 2 - 4 = -1

 

1번째 인덱스에서 실패하게 된다.

4번째 인덱스에서 시작해서 그나마 1번째까지 온것이지만, 0번째에서 시작했으면 더 일찍 실패했지 더 나아가지는 못하는 것이다. 

따라서 다음과 같은 개념을 적용해, 모든 시작 인덱스를 다 테스트해보는 것이 아닌 실패한 지점보다 1만큼 더 나아간 지점에서 테스트하면 훨씬 시간 복잡도를 아낄 수 있다.

 

Solution:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size = gas.size();
        for(int i = 0; i < size;) {
            int current = i; 
            int totalGas = 0;
            for (int step = 0; step < size; step++) {
                current = (step + i) % size; // 출발 점에서 step만큼 이동한 위치
                totalGas = totalGas + gas[current] - cost[current];
                
                if(totalGas < 0) { // i 시작점일 때 current 에서 막힌다.
                    break;
                }
            }

            if(totalGas >= 0) {
                return i;
            }

            if(current < i) {
                break;
            }

            i = current + 1; // 막힌 구간 바로 뒤에서 다시 시작한다.
        }
        return -1;
    }

 

여기서 if (current < i)  break; 의 코드를 이해하기 어려웠다.

현재 코드에서 시작점을 0부터 테스트하고 있다. 그래서 current, 즉 마지막 실패 지점은 항상 i 보다 크기 마련이다. 

만약 totalGas 가 0보다 작아 실패한 지점인 게 확실한 상황에서, current 가 i 보다 작기까지 한다면 이미 배열 끝을 지나 0을 거쳐 한바퀴 돌아 이전에 검사한 영역까지 들어왔음을 의미한다. 

예를 들어 i = 3일때, current = 0인 지점에서 실패했다고 하자. 어짜피 다음 순회를 시작해봤자 current + 1 인 1을 시작점으로 둘 터인데, 그러면 이미 이전에 i = 1일때 검사했던 것과 중복된다. 그래서 더 이상 새롭게 검사할 시작점 후보가 없다는 것을 의미해 break;를 통해 -1을 반환하도록 하는 것이다.

 

이는 이론적으로 O(N^2)의 시간복잡도를 가진다. O(N)의 시간복잡도 풀이는 아래 링크에서 확인할 수 있다.

 

Reference:

https://medium.com/deluxify/leetcode-134-gas-station-11295b36f0cf

Leetcode# 134. Gas Station