LeetCode: 134번 (Gas Station) [JAVA]

문제 링크

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

Gas Station - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 탐색한 구간을 표시할 startIndex, endIndex를 모두 0으로 초기화
2. do while문을 기반으로 현 시점(endIndex)의 위치의 cost와 gas 값을 누적 변수(acc)에 반영하며 계산하고, endIndex를 하나 증가
3. 이후 누적값이 음수라면 startIndex를 앞으로 하나 빼며 해당 위치의 cost와 gas 값을 누적값에 반영하고, 이를 누적값이 양수가 될 때까지 반복
4. 앞선 do while문의 조건으로 startIndex와 endIndex가 만나기 전까지 반복, 이후 결과가 음수라면 -1 반환하고, 아니면 startIndex 반환

 단순히 생각하면 이중 for문을 통해 여러 곳에서 시작 위치를 잡으며 해당 시작 이후 결과가 가능한지 불가능한지를 판별할 수도 있지만, 그런 경우 복잡도가 O(n^2)이 되며 매우 커지기 때문에 다른 방법이 필요하다.

 그러기 때문에 기존의 구간 계산 결과를 최대한 재활용해야 하는데, 기존 연산처럼 구간을 뒤로만 확장하는 것이 아니라 앞으로 확장을 하며 연산을 하면 한 번의 탐색으로 정답을 찾을 수 있다. 우선 구간을 표시할 startIndex, endIndex를 모두 0으로 초기화하고, do while문으로 구간 탐색문을 작성한다. 단순히 현재 위치(endIndex)의 cost와 gas 값을 누적 변수(acc)에 반영하고, endIndex를 하나 증가 시킨다. 이 때 누적값의 결과에 따라 이후가 달라지는데, 만약 누적값이 0보다 작으면 더 이상 뒤로 갈 수 없기 때문에 startIndex를 앞으로 이동시키며 해당 위치의 cost와 gas 값을 누적값에 반영하며 누적값이 0이상이 될때까지 반복한다. 만약 누적값이 0 이상인 상태면 단순히 startIndex와 endIndex가 만날 때까지 endIndex를 뒤로 옮기며 연산을 반복하면 된다.

 이후 탐색이 완료된 후 누적값이 0 미만이면 -1을, 그렇지 않다면 구간의 시작인 startIndex를 반환하면 된다.

 

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length, acc = 0, startIndex, endIndex;

        startIndex = 0;
        endIndex = 0;

        do {
            acc = acc - cost[endIndex] + gas[endIndex];//현 남는 가스가 있다면
            endIndex = (endIndex + 1) % length;//뒤로 이동

            while (acc < 0 && startIndex != endIndex) {//현재 남는 가스가 없다면
                --startIndex;//앞으로 이동

                if (startIndex < 0) {
                    startIndex += length;
                }

                acc = acc - cost[startIndex] + gas[startIndex];
            }
        } while (startIndex != endIndex);

        if (acc < 0) {//최종 결과가 음수라면
            return -1;
        }

        return startIndex;
    }
}

결과