문제

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

구현 전 예상 풀이

• gas = [1,2,3,4,5]
• cost = [3,4,5,1,2]
• extra = [-2, -2, -2, 3, 3]

한 바퀴 돌 수 있는지는 쉽게 구할 수 있다.
시작점은 루프를 돌면서 구하겠다.

class Solution {
   public int canCompleteCircuit(int[] gas, int[] cost) {
       int length = gas.length;
       int[] extra = new int[length];
       int sum = 0;

       for (int i = 0; i < length; i++) {
           extra[i] = gas[i] - cost[i];
           sum += extra[i];
       }

       if (sum < 0) {
           return -1;
       }

       for (int i = 0; i < length; i++) {
           int accumulation = 0;
           for (int j = 0; j < length; j++) {
               int idx = (i + j) % length;
               accumulation += extra[idx];
               if (accumulation < 0) {
                   break;
               }
           }

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

       return -1;
   }
}

시간초과로 통과하지 못한다.

구현 코드

여유 가스가 많은 인덱스부터 루프를 돌도록 알고리즘을 변경했다.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int[] extra = new int[length];
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < length; i++) {
            extra[i] = gas[i] - cost[i];
            map.put(i, extra[i]);
            sum += extra[i];
        }

        if (sum < 0) {
            return -1;
        }

        List<Integer> idxList = map.entrySet().stream()
                .sorted(Comparator.<Map.Entry<Integer, Integer>>comparingInt(Map.Entry::getValue).reversed())
                .map(Map.Entry::getKey)
                .toList();

        for (Integer i : idxList) {
            int accumulation = 0;
            for (int j = 0; j < length; j++) {
                int idx = (i + j) % length;
                accumulation += extra[idx];
                if (accumulation < 0) {
                    break;
                }
            }

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

        return -1;
    }
}

다른 사람 풀이

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sGas = 0, sCost = 0, res = 0, total = 0;
        for (int i = 0; i < gas.length; i++) {
            sGas += gas[i];
            sCost += cost[i];
        }
        if (sGas < sCost) return -1;
        for (int i = 0; i < gas.length; i++) {
            total += gas[i] - cost[i];
            if (total < 0) {
                total = 0;
                res = i + 1;
            }
        }
        return res;
    }
}

참고해서 만든 새로운 풀이

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int res = 0;
        int total = 0;
        int accumulation = 0;

        for (int i = 0; i < gas.length; i++) {
            int extra = gas[i] - cost[i];
            accumulation += extra;
            total += extra;
            if (accumulation < 0) {
                accumulation = 0;
                res = i + 1;
            }
        }

        if (total < 0) {
            return -1;
        }
        
        return res;
    }
}

처음 풀이보다 코드도 쉽고, 시간복잡도나 공간복잡도도 더 나은 결과가 나온다.

134. Gas Station
다른 사람 풀이 링크