[LeetCode] 134. Gas Station - 풀이

난이도: Normal

총평: O(n) 풀이를 생각해내기 힘들다.

 

풀이는 https://leetcode.com/problems/gas-station/editorial 을 보았다.

문제 설명

n개의 가스 스테이션이 원형의 경로를 따라 배치되어 있다. i번째 가스 스테이션에는 gas[i] 만큼의 가스가 있다.

당신은 무제한의 가스가 들어가는 탱크가 탑재된 차로 원형의 경로를 따라 여행을 하려고 한다. 이 때, i번째 가스 스테이션에서 (i+1)번째 가스 스테이션으로 이동하는데 cost[i] 만큼의 가스가 필요하다. 빈 가스 탱크를 가지고 경로에 있는 가스 스테이션 중에 하나에서 출발할 수 있다.

gas와 cost로 이루어진 두 배열이 주어졌을 때, 어떤 가스 스테이션에서 출발해야 시계방향으로 한 바퀴 돌 수 있을까? 만약 그런 가스 스태이션이 존재한다면, 그 가스 스태이션의 인덱스를 반환하고, 아니면 -1을 반환해야한다. 단, 해가 존재할 시 그 해는 유일하다.

 

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.

 

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

풀이

O(n^2)의 Brute-Force 접근

일단 가장 쉽게 문제를 풀려면 모든 가스 스태이션에서 출발하는 상황을 시뮬레이션해보면서 한 바퀴 순회가 가능한 경우를 찾으면 된다. n개의 시작점에서 각각 최대 길이 n의 경로를 탐색해야하므로, $O(n^2)$만큼의 시간이 소요된다.

O(n)안에 해결할 수 있을까?

이제, 더 최적화할 수 있는 방법을 생각해봐야한다. 어떻게 하면 모든 점에서 시도하지 않고 해를 찾아낼 수 있을까?

 

우선 각 위치 i의 gain을 gas[i]-cost[i] 로 정의하자. gain의 총합이 음수라면, 당연하게도 조건을 만족하는 시작점은 없다. 어떤 점에서 출발하든 결국 어느 지점에서 남은 gas의 양보다 cost의 양이 커져 엔진이 꺼지게 될 것이기 때문이다.

 

그렇다면, 만약 gain의 총합이 음수가 아니라면, 조건을 만족하는 시작점이 있을까? 이 질문에는 확실히 대답하기 어려우니 천천히 생각해보자.

 

0번째 지점에서 시작해서 시뮬레이션을 했다고 하자. 그렇다면 어느 지점에서 남아있는 gas의 양보다 cost의 양이 커져 실패할 수 있다.

이 해를 수정하기 위해 '시작점을 움직인다'는 생각에 빠지게 되면 난관에 빠진다. 시작점을 왼쪽으로 밀어서 시작점 이전의 구간에서 연료를 더 벌어오는 것, 시작점을 오른쪽으로 밀어서 시작점 이후의 구간에서 쓰는 연료를 줄이는 것 모두 말이 되기 때문이다. 슬라이딩 윈도우 방식으로 접근할 때 방향이 정해지지 않으므로 문제가 된다.

 

하나 생각해볼 점은, 시뮬레이션을 하다가 연료가 다 떨어진 된 현재 상황, 즉 지금까지 gain의 합이 음수인 상황에서 전체 경로의 gain의 총합이 0 이상이기 때문에 남은 구간의 gain은 양수가 된다. 즉, 남은 구간에서는 연료가 무조건 증가한다. 즉, 지금 시뮬레이션이 실패한 이유는 연료를 충분히 모아놓고 연료를 소모한게 아니라, 연료를 소모하고 연료를 모으는 경로가 되었기 때문이다.

 

연료를 벌 수 있는 구간은 실패한 구간 이후이기 때문에, 다시 실패한 구간 이후를 시작점으로 잡고 시뮬레이션을 수행해볼 수 있다.

이 시뮬레이션은 성공할 수도 있고 실패할 수도 있다. 반복해서 실패한다면

이렇게 gain의 총합이 음수인 구간이 몇 개가 생기게 된다. 하지만 이렇게 연료를 손해보는 구간이 있으면, 그만큼 연료를 이득을 보는 구간이 남아있다. 왜냐하면 gain의 총합이 0 이상이기 때문이다.

 

그래서 결국 연료 이득을 보는 구간을 찾게 된다면, 여기서 번 연료의 양은 이전 구간들에서 본 손해들보다 항상 많다.

따라서, 연료를 이득을 보는 구간을 먼저 수행하고, 연료 손해를 보는 이전 구간을 수행한다면 그게 우리가 찾던 연료를 모두 소비하지 않고 1회 순회가 가능해지는 시작점이 된다. Go로 작성해보면 아래와 같다.

func canCompleteCircuit(gas []int, cost []int) int {
    curr := 0
    total := 0
    j := 0
    for i:=0; i<len(gas); i++ {
        curr += gas[i] - cost[i]
        total += gas[i] - cost[i]
        if curr < 0 {
            j = i + 1
            curr = 0
        }
    }
    if total < 0 { 
        return -1
    } else {
        return j
    }
}