[파이썬 알고리즘 인터뷰][그리디] 주유소

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

주유소를 원형 큐에서 시계방향으로 돌 때, 현재 채울 수 있는 gas와 다음 주유소의 cost로 모든 주유소에 도달할 수 있는 시작점 출력

 

책에서 구현된 코드

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

 

기억해야할 기법

• 조건에 맞는 풀이
  
  • 정답인 출발점이 유일하므로, n번의 탐색으로 확인 가능
  • 속도가 70ms 정도 나옴

 

내가 구현한 코드

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        N = len(cost)
        gas += gas
        cost += cost

        for s in range(N):
            has = 0
            for e in range(s, s+N):
                has += gas[e] - cost[e]
                if has < 0:
                    break
            if has >= 0:
                return s
        return -1

• O(n^2)이며 런타임이 2000ms이 넘어, 위 코드보다 20배 이상 오래걸린다