LeetCode 134 - Gas Station

https://leetcode.com/problems/gas-station

 

n 개의 gas station 원형 루트. gas [i] = gas의 양

i → i + 1 까지 가는데 cost [i] 만큼의 gas 가 필요하다.

어느 지점에서 시작해야 시계방향으로 완주할 수 있을까. 만약 완주가 불가능하다면 -1을 반환한다.

즉 현재 가지고 있는 gas가 cost보다 커야만 이동이 가능하다.

순회하는 것을 표현하는 방법은 몇가지 있겠지만 대표적으로 모듈러 연산을 사용하거나 같은 배열일 이어 붙여서 사이즈를 늘리는 방법이 떠오른다.

가장 간단한 풀이는 모든 점을 시작점으로 삼아 진행해 보는 것이다.

하지만 이 방법은 O(n^2)의 시간복잡도를 갖게 되고 문제 조건에서 n은 10^5이다. 도저히 써먹을 수 없다.

생각해 보자.

만약 총 gas가 총 cost보다 작다면 이거는 어느 지점에서 시작해도 정답을 구할 수 없다.

gas - cost를 순이익이라고 했을 때 누적 순이익 < 0 이 되는 지점이 있다면 그 지점 이전은 시작점이 될 수 없다. 왜냐하면 해당 지점에서 기름이 바닥이 날 것이기 때문이다.

따라서 그다음 지점부터 다시 시작해야 한다.

특히 문제 조건을 다시 유심히 살펴보자. 해결책이 있다면 유일하다는 조건이 있다. 그 다음 지점부터 다시 시작하면 답을 구할 수 있다는 것이다. 어차피 그 이전 지점들은 이미 답에서 탈락했으니까!

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        int currentGas = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            currentGas += gas[i] - cost[i]; // 누적 순이익

            if (currentGas < 0) {
                // 출발점 탈락. 그 이후 점부터 가능
                start = i + 1;
                currentGas = 0;
            }
        }

        return totalGas >= totalCost ? start : -1;
    }
}

최종적으로 O(n)의 시간복잡도를 갖는 풀이가 완성된다.