Leetcode 134) Gas Station

26 May 2021 in Algorithms

• 다른 답안의 증명이 이 포스트의 포인트.. 맨 아래를 확인하세요

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int rotate=0;
        for(int i=0;i<gas.length;i++){
            int sum=0;
            while(gas[i]<cost[i]){
                i++;   
                if(i==gas.length){
                    return -1;
                }
            }
            int j=i;       
            boolean a=false;
            while(sum>=0){
                if(j==i && a){   
                    return i;
                }
                sum+=gas[j];
                sum-=cost[j];
                j++;
                if (j>=gas.length){
                    j=j%gas.length;
                    a=true;
                }
            }
        }
        return -1;
    }
}

다른 답안

• 처음부터 마지막까지 딱 한번씩만 순회하는 아주 신세대 알고리즘.
• sum 은 처음부터 끝까지 음수가 되든 말든 신경 안쓰고 다담는 변수,
• cur은 i번째의 원소들의 차가 음수가 되면 start를 다음 숫자로 바꿔준다.
• sum과 cur이 모두 양수거나 0보다 크면, start를 리턴하고 아니면 그냥 -1을 리턴한다.
• 이 알고리즘이 가능 한 이유는, 원형으로 돌기 때문에. 증명은 코드 아래에!

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int cur = 0;
        int sum = 0;
        int start = 0;
        for(int i = 0; i < gas.length; i++){
            sum += gas[i] - cost[i];
            //cur는 음수이면 초기화된다. 그래서 0임. 이게 내 코드의 sum 변수 같은 역할을한다.
            cur += gas[i] - cost[i];
            if(cur < 0){
                cur = 0;
                //이게 gas.length가 되면, 어차피 for문에서 나가서 cur<0이 돼서 -1이 리턴된다.
                start = i + 1;
            }
        }
        if(cur >= 0 && sum >= 0){
            return start;
        }
        return -1;
    }
}

증명