[그리디 알고리즘] 주유소

134 | Gas Station
https://leetcode.com/problems/gas-station/

 

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

 

 

작성 코드 (시간 초과)

 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        l = len(gas)
        gas *= 2
        cost *= 2
        for i in range(l):
            suc = True
            tank = gas[i]
            for j in range(i, i + l - 1):
                tank -= cost[j]  
                if tank <= 0:
                    suc = False
                    break              
                tank += gas[j + 1]  
            if tank >= cost[i - 1] and suc:
                return i
        return -1

 

• 원형 구조이기 때문에 gas, cost 배열을 두 번 반복하도록 함
• 첫번째 반복문 -> 시작점, 두번째 반복문 -> (주유소의 수 - 1) 만큼 방문 !! 마지막 주유소의 경우 원점으로 돌아가는 것, 가는데 필요한 연료만 계산하면 돼서 따로 뺌!
• 현재 tank (연료) 에서 cost[j] 이동 시 필요한 연료를 뺐을 때 tank 가 0보다 작거나 같다면 갈 수 없으니 suc 를 False 로 바꾸고 break
• 만약 tank 가 0보다  크다면 tank 에 도착한 곳의 연료 gas[j + 1] 를 더해줌
• 다 끝나고 마지막 주유소에서 가는데 필요한 연료만 계산하면 됨, 같아도 됨 ! suc 가 TRUE 여야 모든 주유소를 방문한 것이니 조건문에 추가 (뒤늦게 든 생각인데 suc 를 and 앞에 두는 것이 효율적이었을 듯)
• 단 한가지의 경우만 만족하므로 만족하는 값이 있으면 바로 return
• 만약 반복문을 다 돌아도 return 되지 않았으면 없는 것이니 -1 return

 

참고 코드

 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for start in range(len(gas)):
            fuel = 0
            for i in range(start, len(gas) + start):
                index = i % len(gas)

                can_travel = True
                if gas[index] + fuel < cost[index]:
                    can_travel = False
                    break
                else:
                    fuel += gas[index] - cost[index]
            if can_travel:
                return start
        return -1

 

• 큰 차이가 있다면 % 를 통해서 index 오류가 안 뜨게 함 -> 원형 구조의 경우 유용!
• 이 코드도 시간 초과 발생

 

 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 모든 주유소 방문 가능 여부 판별
        if sum(gas) < sum(cost):
            return -1

        start, fuel = 0, 0
        for i in range(len(gas)):
            # 출발점이 안되는 지점 판별
            if gas[i] + fuel < cost[i]:
                start = i + 1
                fuel = 0
            else:
                fuel += gas[i] - cost[i]
        return start

 

• O(n) 풀이 
• 초반에 바로 방문 여부 바로 판별하기 -> 반드시 존재하는 경우만 남음
• 반드시 한 군데에서는 성립함 -> 만약 출발점이 안 되는 지점이 나온다면 start 에 i + 1 값 저장해줌
• 돌면서 앞 부분이 실패할 경우는 없음 어차피 답이 하나만 나옴!! 현재 앞 부분은 나중에 돌 for 문에서도 누적될 것이기 때문에 무조건 성공했을 것임