[LEET CODE 150] - 134 Gas Station

LeetCode의134번인 "Gas Station" 문제를 풀어봤다.

그리디 알고리즘을 활용한 문제풀이다.

 

문제 요약

원형으로 배치된 N개의 주유소가 있다. 각 주유소 i 에서 gas[i] 만큼의 연료를 얻을 수 있고, 다음 주유소 (i + 1)로 이동하는 데 cost[i] 만큼의 연료가 필요하다. 자동차는 빈 탱크 상태로 출발하며, 자동차는 빈 탱크 상태로 출발하며, 어떤 주유소에서 출발하면 한바퀴를 완주할 수 있는지를 구하라.

• 가능하면 출발 주유소의 인덱스를 반환
• 불가능 하면 -1 반환

정답 코드(Python)

class Solution:
	def canCompleteCircuit(self, ges:List[int], cost:[List[int]) -> int:
    if sum(gas) < sum(cost):
    	return -1
        
    total = 0
    res = 0
    
    for i in range(len(gas)):
    	total += (gas[i] - cost[i])
    
    if total <0:
    	total = 0
        res = i + 1
    return res

 

코드 아이디어

1. 전체 가능성 체크

if sum(gas) < sum(cost):
	return -1

 

• 전체 가스 총합이 전체 비용 총합보다 작으면 어떤 시작점에서도 완주 불가.
• 이 체크는 " 필요 충분 조건의 필수조건" 이고, 이후 그리디로 시작점을 찾을수 있게 해줌.

2. 그리디로 시작점 찾기

total += gas[i] - cost[i]

if total < 0:
	total = 0
    res = i + 1

한바퀴로 돌면서 "현재 후보 시작점에서 출발 했을 때 남는 연료(total)를 누적해.

 

만약 중간에 total < 0 이 되면

• 현재 시작점 res에서 출발해서 i까지 왔는데 연료가 음수가 됐다면, res부터 i사이의 어떤 지점 k에서 시작해도 i+1 까지 못간다.

정리

• sum(gas) >= sum(cost)면, 적어도 한 곳에서는 시작이 가능함.
• total < 0이 되는 순간, 현재 후보 시작점부터 그 지점까지의 모든 시작점은 실패한다.
• 그래서 후보를 i+1로 넘기는 걸 반복하면, 마지막 남은 후보가 유효 시작점이 된다.