leetcode.com 134. Gas Station

문제 링크: https://leetcode.com/problems/gas-station/description/

파이썬 소스: https://bit.ly/49LqQDH

 

이 문제의 길이가 10⁵ 이기 때문에, 모든 gas station에서 출발해서, 모두 방문해 O()는 아래와 같습니다.

O(10⁵ * 10⁵) = O(10¹⁰)

완전탐색을 통해서 모두 방문해서는 문제의 답을 구할 수 없습니다.

 

자 그러면, i 번째에서 i+1 번째로 갈수 없는지 알아 보려면,

gas[i] < cost[i] == True

True 가 되면 갈 수 없습니다.

 

그러면 0 번째부터 n 번째 까지 모두 더해 보는 거죠.

gas[0] < cost[0]

gas[1] < cost[1]

…

gas[n-1] < cost[n-1]

위의 모두를 위의 방향에서 아래 방향으로 더해보면,

sum(gas) < sum(cost)

위의 식이 됩니다. 위의 식이 True이면 이 문제의 답을 구할 수 없으므로 -1을 리턴합니다.

False인 경우에는 답을 구할 수 있으므로, 어디서 시작해야 할 지 시작할 gas station을 찾아야 합니다.

 

여기서, 다시한번 문제의 의도를 잘 파악해야 하는 문구가 있습니다.

If there exists a solution, it is guaranteed to be unique

 

즉, 반드시 특정 한 개의 gas station에서 출발해야, 마지막 gas station까지 도달 할 수 있고, 그렇지 않은 다른 경우는 모두 마지막 gas station까지 도달할 수 없습니다.

 

from typing import List class Solution:     def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:         if sum(gas) < sum(cost):             return -1         start = 0         fuel = 0         for idx in range(len(gas)):             fuel += (gas[idx] - cost[idx])             if fuel < 0:                 fuel = 0                 start = idx +1         return start

 

Idx가 0번일 때, fuel < 0이 True인 경우가 생겼다면, 0번은 start는 최소한 0번은 아닙니다.

Idx가 1번일 때, 부터 시작해서, n-1까지 모두 이동해 보니, fuel < 0이 True가 되는 경우가 없었다고 가정해 보겠습니다.

그러면 여기서 고민은 0번에서 1로 이동할 수 있느냐? 이것이 고민될 수 있습니다.

하지만, 이미 sum(gas) < sum(cost) 이 식이 False 인 경우에만 위의 루프가 실행되게 됩니다.

1) sum(gas) < sum(cost) == False

바꿔 적으면 2) sum(gas) >= sum(cost) == True인 상태이구요.

0 번에서 1번으로 이동할 수 없으려면, 아래 3번식이

3) gas[0] + sum(gas[1:]) >= cost[0] + sum(cost[1:]) 이 False가 되어야 하지만, 이미 1)과 2)에 따라서, 3)식이 False 가 될 수 있는 경우는 존재 하지 않습니다.

즉, idx 1번이 답이라면, 0 에서 1로는 반드시 이동 가능하거나, idx 1번이 답이 아닌 경우만 존재하게 됩니다.

Idx 1번이 답이 아닌 경우를 풀어보면, 2~n-1 중에 fuel <0 True가 되지 않는 값이 1개 존재하게 됩니다. 따라서, 이를 idx 0 의 경우 뿐만 아니라, 0, 1 이렇게 확장해 보면, 루프 하나로 답을 구할 수 있게 됩니다.

 

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul