[그리디] Leet code 134. Gas Station

리트코드 134번
주요소를 연료고갈 없이 한바퀴 돌 수 있는 시작점 구하기

풀이 1. 투포인트

• 시작점, 끝점 초기화 : 맨끝

• 차액계산 -> gas[1,2,3,4,5] - cost[3,4,5,1,2] = [-2,-2,-2,3,3]

• 차액이 음수가 되지 않도록 순서를 정해주면 된다!

• 차액들의 sum이 음수면 방법은 없는 것 -> -1반환

• total : 시작점과 끝점사이에 차액의 합

• 알고리즘

  • total이 양수면 : 끝점 옮기기 tail + 1
  • total이 음수면 : 시작점바꾸기 head - 1
  • tail - head 가 size-1이 되면 끝난 것

• 그리디 : 매번 total가격을 보고 head값 조정 or 그대로 유지 결정

class Solution:
    def canCompleteCircuit(self, gas , cost) -> int:
        size = len(gas)
        sub_list = [ gas[i] - cost[i] for i in range(size)] # 차액계산

        # 예외처리
        if sum(sub_list) < 0 :
            return -1
        if len(sub_list) == 1:
            return 0


        #시작점
        head, tail = size-1, size-1
        total = sub_list[head]

        while tail - head != size-1: # 사이즈가 다다르면 끝
            if total >= 0: # 차액이 음수가 아니면 : 유지
                tail += 1
                total += sub_list[tail % size]
            else: # 차액이 음수이면 : 시작점 옮기기
                head -= 1
                total += sub_list[head]


        return head