[Python] #134. Gas Station(Medium)

문제 

이 문제는 첫 가스탱크에 0이 있을때 어느위치에서 시작해야 한바퀴를 다 돌고 올수있는지 있다면 어느지점에서 시작해야하는지 한바퀴 못돈다면 False를 출력하는 문제이다.

 

처음 시도한 방법은 circle이라는 함수를 만들어서 각 index별 한바퀴를 순회할수있는지를 확인하는 방법으로 프로그램을 작성했다. 

 

class Solution:
    def canCompleteCircuit(self, gas, cost) -> int:
        for i in range(len(gas)) :
            if self.circle(i,gas,cost):
                return i
        return -1
    def circle(self,index,gas,cost):
        n = len(gas)
        i_g = 0
        j = 0
        
        if gas[index] < cost[index]:
            return False
        for i in range(n+1):
            if j == 0 :
                pass
            else:
                i_g -= cost[index]
                index += 1
            if index == n :
                index = index % n 
            
            if i_g < 0 :
                return False
            i_g += gas[index]
            j += 1

        return True

확인하는 방법은...

해당 index에서부터 한바퀴를 순회하면서 가스 채우고 cost를 빼면서 음수값이나오면 for문을 벗어난다.

 

결과

결과는;; 풀긴 풀었으나 엄청나게 오랜 시간이 걸린다....

고민에 고민을 했지만... 어떻게 접근해야할지 모르겠어서 고수님들의 답을 참고했다. 

class Solution:
    def canCompleteCircuit(self, gas, cost) -> int:
        n = len(gas)
        tank = 0
        diffsum = 0
        index = 0
        for i in range(n):
            tank += gas[i] - cost[i]
            diffsum += gas[i] - cost[i]
            if tank < 0 :
                tank = 0
                index = i + 1
        return index if index < n and diffsum>= 0 else - 1

방식은 tank에 0, diffsum= 0, index =0으로 초기화한다.

for문을 통해 tank에 gas를 더하고 cost를 빼준다.

diffsum에도 gas와 동일하게 계산을 한다. 

만약 tank의 값이 음수일경우 tank의 값을 0으로 초기화하고 index값을 i+1로 만들어준다.

결과