리트코드 - 134. Gas Station

리트코드 - 134. Gas Station

출처 - https://leetcode.com/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

원형 루트에 따라 n개의 주유소가 있는데, i번째 주유소의 가스량은 gas[i]입니다.
제한 없는 가스 탱크가 달린 자동차가 있어서 i번째 주유소에서 다음(i+1)번째 주유소까지 가는 데에는 cost[i]의 가스 비용이 듭니다. 이 여행을 한 주유소에서 빈 탱크로 시작합니다.
두 정수 배열 gas와 cost가 주어지고 한 번의 시계 방향 주행으로 주위를 돌아 다닐 수 있는 주유소 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다. 해결책이 있다면 고유할 것입니다.

 

의사코드

int totalGas = 0 // 전체 Gas int curDif = 0  // 현재까지 Gas 양 int difGas = 0 //  gas에서 cost 뺀 Gas 차이 int startIndex = 0  // 순회가 가능한 정답 인덱스 반복문 시작 (i = 0부터 +1씩 증가, i < gas.length까지)     difGas = gas[i] - cost[i]     totalGas += difGas     curDif += difGas     if (curDif < 0)         curDif = 0         startIndex = i + 1 반복문 종료 if (totalGas < 0)     -1 리턴 startIndex 리턴

 

풀이코드

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int curDif = 0;
        int difGas = 0;
        int startIndex = 0;
        for (int i = 0; i < gas.length; i++) {
            difGas = gas[i] - cost[i];
            totalGas += difGas;
            curDif += difGas;

            if (curDif < 0) {
                curDif = 0;
                startIndex = i + 1;
            }
        }

        if (totalGas < 0) {
            return -1;
        }
        return startIndex;
    }
}

코드설명

자동차가 한 바퀴를 돌 수 있는 인덱스를 구하는 문제이다.

이를 다시 두 개의 문제로 나누어 볼 수 있다.

1. 자동차가 한 바퀴를 돌 수 있는가

2. 한 바퀴를 돌 수 있을 때 돌 수 있는 인덱스가 무엇인가

 

1과 2를 한꺼번에 처리하려고 하면 queue와 같은 방법을 생각해 볼 수도 있지만 너무 로직이 복잡해진다.

두 조건을 각각 확인해서 둘다 옳은 경우 한바퀴를 돌 수 있을 것이다.

 

1. 먼저 자동차가 한 바퀴를 돌 수 있는 조건은 간단하다. gas에서 cost를 뺀 값들을 모두 더해서 0보다 크거나 같으면 돌 수 있다.
gas에서 gas가 +되고, cost 에서 - 되기 때문에 이 값이 실제 자동차에 남아있는 기름의 양이 된다.

아래 초기코드 부분을 보면 조금 이해가 빠를 것이다.

 

2. 다음으로 돌 수 있는 인덱스를 찾아야 한다.

정확히 말하면 시작점의 조건을 찾는 것인데 우선 간단히 생각하면 gas가 cost보다 크다면 출발할 수 있을 것이다.

 

문제는 출발한 이후에 중간에 끊길 수가 있다는 것이다.

문제에 주어진 예시로 설명해보면,

gas = [1,2,3,4,5], cost = [3,4,5,1,2] 로 이므로 gas - cost 한 값의 sum 배열을 따로 만들어보자.

sum = [-2,-2,-2,+3,+3] 이 될텐데, 이렇게 되면 3번째 인덱스에서 gas가 cost보다 크고 올바른 출발값이 된다.

 

하지만 만약 sum = [+3,-2,-2,-2,+3] 이런식으로 계산되는 gas와 cost가 주어진다면,

0번째 인덱스에서 출발할 수 있지만 인덱스 2번째에서 끊기게 되어버린다.

따라서 출발점부터 하나씩 더했을때 0보다 크거나 같아야 한다.

 

즉, 두 가지를 정리하면 gas가 cost보다 큰 값을 후보로 두고 ,이 인덱스부터 더한 값이 반드시 0보다 같아야 한다.

 

이제 코드로 보면 gas배열을 순회하는데

difGas에서는 sum 배열을 두는 대신 직접 값을 가지는 변수로 두고 이 값을 totalGas에도 추가하고, curDif에도 추가했다.

 

만약 curDif가 0보다 작아진다면 다음 인덱스가 출발 인덱스의 후보이므로 startIndex를 i + 1 값으로 두었다.

이렇게 순회를 한 다음 totalGas가 0보다 작은 경우는 1. 자동차가 한 바퀴를 돌 수 있는가에 위배되므로 -1을 리턴한다.

그게 아니라면 startIndex가 정답이 된다. totalGas가 0보다 크면 startIndex가 없는 경우는 없다.(문제조건)

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        int curGas = 0;
        int startIndex = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            curGas += gas[i] - cost[i];

            if (curGas < 0) {
                curGas = 0;
                startIndex = i + 1;
            }
        }

        if (totalGas >= totalCost) {
            return startIndex;
        }
        return -1;
    }
}

totalGas와 totalCost를 나누어서 풀었더니 3ms가 나왔다.

직관적으로 이해가 가기는 쉬웠으나 런타임이 하위라서 개선할 부분을 찾아보았다.

totalCost 부분을 제외하고, totalGas만으로 판별하는 풀이 코드 방식으로 변경했더니 1ms가 나왔다.

 

정리

배열을 여러번 순회하지 않고, 한 번 순회만으로 조건을 만족하는 경우를 각각 찾아 만족하는 로직을 작성하는 방법.