[리트코드] 134. Gas Station

문제

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

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

---

✔ 문제접근 #1 그리디[통과] ⭕

Intuition
diff = gas - cost 를 구한다음 계속해서 전진할 수 있는지 판단한다.

Algorithm

gas - cost에서 diff 배열을 구한다. diff[i]는 현재 위치에서 다음칸으로 뛰어넘을 때 남는 연료를 의미한다.

diff배열의 총합이 0보다 작다면 애초에 불가능하기 때문에 -1을 리턴한다.

 

앞에서 부터 순회하며, 해당 index위치에서 출발할 수 있는지 확인한다.  출발가능 하다면 해당 위치의 값을 start에 저장하고 fuel에 diff[i](남는 연료)를 누적해간다. 만약 중간에 이동이 불가능하다고 판단되면 start는 해당위치에서 다시 초기화, fuel은 0으로 초기화한다.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {   

        // gas - cost 를구한다
        int n = gas.length;
        int[] diff = new int[n];
        for(int i = 0; i < n; i++) {
            diff[i] = gas[i] - cost[i];
        }
        
        
        if (Arrays.stream(diff).sum() < 0 ) {
            return -1;
        }
        
        
        // for문 한번으로 해결해보자.
        int fuel = 0;
        int start = 0;
        for(int i = 0; i < n; i++) {
            if ((fuel + diff[i]) < 0) {
                fuel = 0;
                start = i + 1;
            } else {
                fuel += diff[i];
            }

        }
        
        return start;
    }
}

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • diff배열 구하기 O(N)
  • 전체 배열크기만큼 순차탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(N)
  
  • gas, cost의 크기만큼 diff배열 사용

---

기타풀이 및 회고

이 문제도 시간복잡도에 걸리기 때문에 O(N) 혹은 O(NlogN)에 해결할 수 있는 방법을 생각해야 되는 문제였다. 결과적으로 그리디 였고 푸는데 꽤 오래 걸렸다. 그리디는 잘 모아뒀다가 무조건 익숙해질때까지 복습복습!

 

문제에서 이동할 때 드는 비용이라는 내용이 나왔는데, 해당 위치에서 어떤 비용이 든다? 라는 문제는 누적합이나 혹은 소모되는 비용의 차이를 계산해서 풀었을 때 좋은 접근을 할 수 있었던 기억이 많이 있는 것 같다. 참고해서 더 빨리 아이디어를 떠올릴 수 있도록..!