134. Gas Station

134. Gas Station

 

https://youtu.be/lJwbPZGo05A?si=AM0Po-ey6yqofKrN

class Solution:
    def canCompleteCircuit(self, gas: 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
        
        # 추가 검증 코드
        total = 0
        for i in range(res, res + len(gas)):
            idx = i % len(gas)  # 원형 경로 처리
            total += gas[idx] - cost[idx]
            if total < 0:
                return -1  # 만약 부족하면 완주 불가
        
        return res

 

추가 검증 코드가 필요 없다고 함.!!

 

추가 검증 코드 없이 왜 충분한가?

1. res는 가능한 시작점으로 보장됨

• 루프에서 total이 음수가 되는 순간 이전 주유소들(인덱스 0부터 i)에서 출발하면 연료가 부족하다는 것을 알고, 다음 주유소(i + 1)를 새로운 시작점으로 갱신합니다.
• 이후 남은 루프는 res부터 끝까지 연료를 계산하며, 전체적으로 충분한 연료가 보장되므로 res는 완주 가능한 유일한 시작점입니다.

2. gas[i]와 cost[i]의 직접 접근

• 처음부터 끝까지 모든 주유소를 한 번만 순회하면, gas와 cost를 직접 접근하여 충분한 정보를 얻을 수 있습니다.
• 이미 res 이전의 주유소는 계산 중 음수(total < 0)가 되었기 때문에 고려할 필요가 없습니다.

class Solution:
    def canCompleteCircuit(self, gas: 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