리트코드 134 Gas Station (파이썬)

https://leetcode.com/problems/gas-station/

Gas Station - LeetCode

 

---

풀이

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        
        # 만약 gas의 총 합이 cost의 총 합보다 작다는 것은, 어느 칸에서든 한 바퀴를 못돈다는 것이다.
        if sum(gas) < sum(cost):
            return -1

        # start는 인덱스 번호, fuel은 누적된 가스의 양
        start, fuel = 0, 0
        for i in range(len(gas)):
            # 현재 인덱스에서 다음 인덱스로 가지 못하면,
            # start를 다음 인덱스로 지정해주고 fuel은 0으로 초기화
            if gas[i] + fuel < cost[i]:
                start = i + 1
                fuel = 0
            # 갈 수 있는 경우, fuel에 값을 저장
            else:
                fuel += gas[i] - cost[i]

        return start

 

---

해설

• 생각을 해보면 총 가스의 양이 총 비용보다 낮으면 어느 위치에서 출발하던지 한 바퀴를 돌 수가 없다.
• 이 경우 바로 -1을 return
• 밑의 과정이 설명하자면 복잡한데, 직접 그려보며 생각해본다면 이해할 수 있다.
• for문에 온 상태라는 것은, 한 바퀴를 돌 수 있는 정류장이 하나 이상은 존재한다는 것이다.
• 이 점을 잘 생각해서 코드를 짜면 된다.