[알고리즘] 주유소
3621 단어 알고리즘파이썬 알고리즘 인터뷰그리디 알고리즘그리디 알고리즘
책 풀이
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
전체 기름의 양이 전체 비용보다 클 경우 반드시 전체를 방문할수 있는 출발점이 존재한다. 원래는 여러 곳이 될 수 있겠지만 이 문제에는 출발점이 유일하다는 제약이 있으므로, 여기서는 반드시 한 군데만 존재하게 된다. 비용이 더 큰 경우는 초기에 예외처리를 해준다.
이 문제는 한 번 이상은 반드시 성립되지 않는 지점이 존재한다. 그렇지 않다면 정답이 복수개가 되기 때문이다. 성립되지 않는 지점이 있다면 그 앞은 전부 출발점이 될 수 없다.
Author And Source
이 문제에 관하여([알고리즘] 주유소), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@injoon2019/알고리즘-주유소저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)