[Leetcode] 리트코드 - 주유소(gas-station) 파이썬(python) 풀이

문제

원형으로 경로가 연결된 주유소 목록이 있다. 각 주유소는 gas[i] 만큼의 기름을 갖고 있으며, 다음 주유소로 이동하는데 cost[i]가 필요하다. 기름이 부족하면 이동할 수 없다고 할 때 모든 주유소를 방문할 수 있는 출발점의 인덱스를 출력하라. 출발점이 존재하지 않을 경우 -1을 리턴하며, 출발점은 유일하다.

입력 : gas = [1,2,3,4,5], cost = [3,4,5,1,2]
출력 : 3

설명
3번 인덱스(기름을 4만큼 충전할 수 있는)에서 출발할 경우는 다음과 같다.
3번 → 4번 -1 fuel 3
4번 → 0번 -1 fuel 6
0번 → 1번 -1 fuel 4
1번 → 2번 -1 fuel 2
2번 → 3번 -1 fuel 0
정확하게 기름이 0까지 소모되며, 모든 주유소를 방문할 수 있다.

코드

모두 방문

from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        for start in range(len(gas)):
            fuel = 0
            for i in range(start, len(gas) + start):
                index = i % len(gas)

                can_travel = True
                if gas[index] + fuel < cost[index]:
                    can_travel = False
                    break
                else:
                    fuel += gas[index] - cost[index]
            if can_travel:
                continue
            return start
        return -1

한번 방문

from typing import List


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

풀이

모두 방문

처음부터 한 칸씩 출발점으로 지정하고, 나머지 모든 주유소를 방문하는 방법으로 풀이한다. 주유소의 경로는 원형으로 연결되어 있다고 생각할 수 있으므로, 나머지 연산을 하여 인덱스를 다시 0부터 지정할 수 있게 한다. 그리고 모든 주유소를 방문 가능한지 점검하고, 가능할 경우 이 문제에서는 출발점이 유일하다는 제약이 있기 때문에, 즉 정답이 한 군데이기 때문에 바로 해당 출발점을 결과로 리턴한다. 만약 중간에 끊길 경우 다시 다음번 출발점으로 이 작업 반복한다.

두 번의 루프가 중첩되어 있으므로 O(n²)이다. 이 풀이는 실행 속도가 빠르지 않다. 겨우 풀리는 수준이다. 좀 더 최적화가 필요하다.

한번 방문

전체 기름의 양이 전체 비용보다 클 경우 반드시 전체를 방문할 수 있는 출발점이 존재한다. 원래는 여러 곳이 되 수 있게씨만 이 문제에는 출발점이 유일하다는 제약이 있으므로, 여기서는 반드시 한 군데만 존재하게 된다.

if sum(gas) < sum(cost):
    return False

이렇게 비용이 더 클 때 리턴해버리면, 이제 반드시 존재하는 경우만 남아 있게 된다. 따라서 전체를 방문하면서 성립되지 않는 경우는 출발점을 한 칸씩 뒤로 밀어낸다. 성립되지 않는 지점을 제외하면서 출발점을 찾는다.

예제에서 0, 1 ,2는 안되서 한 칸씩 뒤로 밀어내게 되고, 3에서 부터 성립된다. 그리고 정답을 리턴하게 되는데 이 때 3, 4가 끝난 뒤 0, 1, 2에서 기름이 부족할거라는 걱정을 할 필요가 없다. 출발점은 유일하며, 0, 1, 2는 이미 안되서 한칸씩 밀어냈었다. 또한 4부터 시작해도 정답이 될수도 있다는 생각을 할 수 있는데, 앞쪽까지의 비용이 -라면 어차피 정답이 되지 못하고 한 칸 뒤로 밀어낼테고, 적어도 가진기름과 비용이 딱 맞아 떨어지거나 오히려 남아야(+) 되기 때문에 3부터 시작하더라도 4쪽에서 기름을 잃을 일은 없다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]