Gas Station

Gas Station

Gas Station - LeetCode

- 질문 내용 : N개의 Gas Station이 있고 N index의 Gas Station에서 충전 가능한 Number와 다음 Station까지 가는데 필요한 Number가 주어질때 어는 Gas Station에서 출발 해야 한바퀴를 돌 수 있는가?

- 접근 방법

• 전 순환 : 0~N 까지의 모든 포인트에서 출발해서 돌아올 수 있는지 여부를 확인 하면 된다. O(n^2)

 

• Prefix Sum : 충전 가능한 값 - Cost 값을 사용해서 양수일 경우만 출발해서 돌아올 수 있는지 확인

처음 접근은 Prefix Sum이었다. 이경우에 모든 PrefixSum Cost가 양수인 경우만 처리하면 된다. 음수이면 어짜피 출발이 불가능 함으로 검색하지 않으면 된다. 모든 경우가 음수이면 O(N)이다. 만약 모든 경우가 양수이면 역시 O(N)이다. Index 0에서 이미 한바퀴를 돌면서 Search하고 종료 하기 때문이다. 만약 양수가 N/2라고 해도 O(2*N)이 됨으로 N^2은 발생하지 않는다. 

function canCompleteCircuit(gas, cost) {
    let prefix = new Array(gas.length);
    let gasCircle = new Array();
    let costCircle = new Array();

    gasCircle = [...gas, ...gas];
    costCircle = [...cost, ...cost];

    for (let i = 0; i < gas.length; i++) {
        prefix[i] = gas[i] - cost[i];
    }

    for (let i = 0; i < gas.length; i++) {
        if(0 <= prefix[i]){
            if(canLoop(i)) return i;
        }
    }

    return -1;

    function canLoop(idx) {
        let tank = 0;

        for (let i = idx; i < idx + gas.length; i++) {
            tank += gasCircle[i];
            tank -= costCircle[i];
            if(tank < 0) return false;
        }

        return true;
    }
}

 

• 마지막 최적화 방법은 모든 포인트를 통과하기 위한 Cost는 어디서 시작하든 동일하다는 내용에서 착안이 가능하다. 즉, 충전하는 모든 Gas의 양 - 소모하는 Cost의 양이 반듯이 양수가 되어야 답이 존재 하는거고, 만약에 양수가 된다면 어디서든 최소한 하나의 답은 있게 된다.

이런 측면에서 접근을 하게 되면 다음과 같이 2가지를 확인 하면 된다.

1. 모든 Gas - Cost를 더한다
2. 모든 포인트에서 Gas와 Cost의 차를 Tracking한다. 한번이라도 음수가 나오면 즉시 Starting Point를 다음 포인트로 변화 하고 다시 시작한다.

var canCompleteCircuit = function(gas, cost) {
    let totalCost = 0;
    let startPoint = 0;
    let curGasTank = 0;
    
    for(let i = 0; i < gas.length; i++){
        curGasTank += gas[i] - cost[i];
        totalCost += gas[i] - cost[i];
        
        if(curGasTank < 0){
            curGasTank = 0;
            startPoint = i+1;
        }
    }
    
    return 0 <= totalCost ? startPoint : -1;
};

그런데 만약 이 문제가 다시 나온다고 해도 나는 마지막 방법으로 풀진 못할것 같다.

왜냐하면 음수가 나와서 startPoint가 변화하는 시점 이전에 양수가 나올 수도 있는 포인트가 있다고 생각하기 때문이다.

물론 해당 문제의 Test Case를 아무리 생각해 봐도 그런 경우는 없다는 걸 알지만, 직관적으로 수학적으로 무결한 답이라고 해당 문제를 푸는 동안 결론 내릴 수 있을 지는 자신이 없다.