[리트코드] 22. Gas Station

# 문제 설명

n개의 원형으로 이어진 주유소들이 있다. 각 i번째 주유소에는 gas[i]만큼의 연료를 가지고 있다.

한도가 없는 연료 탱크를 가진 차를 가지고 있을 때, i에서 i+1번째의 주유소에 가기 위한 각 비용은 cost[i]다.

한 주유소에서 빈 연료 탱크를 가지고 여행을 떠나려고 한다.

시계방향으로 주유소들을 모두 한 번 돌 수 있으면 그 시작 주유소 index를, 아니면 -1을 반환해라.

 

(아래) 참고 링크. Discuss 풀이- 연료 계산

 

# 입출력 예시

입력	출력
gas = [1,2,3,4,5] cost = [3,4,5,1,2]	3
gas = [2,3,4] cost = [3,4,3]	-1

 

# 코드 풀이 1.  Brute Force- O(n^2)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for i in range(n):
            totalFuel = 0 # 남은 연료
            stopCount = 0 # 거쳐간 주유소 수
            j = i
            while (stopCount < n): 
                totalFuel += gas[j % n] - cost[j % n]
                if (totalFuel < 0): break
                stopCount += 1
                j += 1

            if (stopCount == n and totalFuel >= 0): return i
        return -1

 

# 코드 풀이 1.  O(n)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n, total_surplus, surplus, start = len(gas), 0, 0, 0
        
        for i in range(n):
            total_surplus += gas[i] - cost[i] # 전체 한 번 travel
            surplus += gas[i] - cost[i] # i에서 i+1로 travel
            if surplus < 0:
                surplus = 0
                start = i + 1
        return -1 if (total_surplus < 0) else start

• surplus는 i에서 i+1 이동할 수 있는지 파악하여, 시작 주유소가 될 수 있는지 계산한다.
• total_surplus는 전체 주유소들을 한 번 돌면서 모두 순회가능한 지 계산한다.

 

 

# 핵심 포인트

• 주유소들이 원형으로 이어져 있기 때문에 index % n 로 각 주유소에 접근한다.
• 다음 주유소로 갔을 때의 연료량에 따라 답이 갈라지므로 어떻게 하면 효율적으로 순회할 지 고민한다.

 

참고 링크. 
https://leetcode.com/problems/gas-station/discuss/1706142/JavaC%2B%2BPython-An-explanation-that-ever-EXISTS-till-now!!!!

[Java/C++/Python] An explanation that ever 🏎 EXISTS 🚕 till now!!!! - LeetCode Discuss