[LeetCode] 134. Gas Station

Ho__sing·2023년 5월 23일

문제해결 자체 재수강

목록 보기

11/39

Intuition

일단, gas[i]보다 cost[i]가 크다면 시작자체가 불가능하므로 그 지점은 답이 될 수 없다. 마찬가지로 $i^{th}$ station에서 $(i+1)^{th}$ station으로 이동할때에도 gas[i]만큼 채우고 cost[i]만큼 소모하므로, 고려해야할 것은 결국 gas[i]-cost[i]의 값이다. 이 값이 그때그때의 상황에서 얼마나 이득 또는 손실을 보는지를 알려주는 것이다.

Approach

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
위와 같은 상황에서 gas - cost = [-2, -2, -2, 3, 3]이다.
gas[i]-cost[i]는 $i^{th}$ station에서 $(i+1)^{th}$ station으로 이동할 때 gas의 변화량이다.

그리고 이 station들을 한바퀴 돌게 되면 gas - cost 배열의 모든 값들을 차례대로 한번씩 더하게 된다. 위의 예시 같은 경우는 $-2_{0^{th}}-2_{1^{st}}-2_{2^{nd}}+3_{3^{rd}}+3_{4^{th}}=+3_{3^{rd}}+3_{4^{th}}-2_{0^{th}}-2_{1^{st}}-2_{2^{nd}}=0$ 이므로 세번째 station에서 출발하면 마지막에 딱 맞게 gas를 소모하며 원점으로 되돌아올 수 있다는 점을 알 수 있다.

그렇다면 만약 gas - cost = [-1, -1, 1]인 경우는 어떨까, 이럴 때는 -1 두개와 +1을 어떻게 합하든 음수가 나온다. 즉, gas - cost의 총합이 0이상일 때만 답이 존재한다는 것이다.
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int res, total=0 ...;
    for (int i=0;i<gasSize;i++){
        total+=gas[i]-cost[i];
        ...
    }
    if (total<0) res=-1;
    return res;
}

이번에는 답이 존재하는 경우에 대해서 집중해보자.
일단, 답이 될 수 있는 후보지는 gas - cost의 값이 양수인 지점이다.

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int res, total=0, sum=0;
    for (int i=0;i<gasSize;i++){
        total+=gas[i]-cost[i];
        if (gas[i]-cost[i]>0&&...) res=i; // 정답 후보지
		...
    }
    if (total<0) res=-1;
    return res;
}

이제 정답 여부를 체크해야한다. 이해를 위해서 $gas - cost = [-2_{0^{th}}, 3_{1^{st}}, -2_{2^{nd}}, 1_{3^{rd}} -3_{4^{th}}, 3_{5^{th}}]$ 인 경우를 예시로 들어보겠다. 답이 될 수 있는 후보지 1번 인덱스부터 차례대로 값을 더하기 시작하면 4번 인덱스에서 -1로 값이 음수가 된다. 1번 인덱스는 답이 아니었던 것이다.
그렇다면 다음 정답 후보지를 정하기 위해 어떤 인덱스를 봐야할까, 정답은 음수가 나올때까지 계산했던 4번 인덱스의 다음인 5번이다. 중간 인덱스는 볼 필요가 없다. 가령, 1번 부터 4번까지 더하는 과정에서 $1_{3^{rd}}$ 에 도달했다는 것은 이전까지의 계산 값이 양수였음을 의미한다. $\alpha+1_{3^{rd}}$ 을 갖고도 4번째 값과의 계산 이후 음수가 되었는데, $1_{3^{rd}}$ 만 가지고 4번째 값과 계산을 한다면 음수가 되는 것은 자명하기 때문이다.

정리하자면, 정답 후보지에서 음수가 나올때까지 값을 더하고 음수가 나온다면 이어서 다음 인덱스부터 정답후보지를 다시 찾아나가면 된다는 것이다.
그리고 정답이 반드시 존재하는 상황이기 때문에, 배열을 처음부터 끝까지 한 번 살펴보면 답을 구할 수 있다.
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int res, total=0, sum=0;
    for (int i=0;i<gasSize;i++){
        total+=gas[i]-cost[i];
        if (gas[i]-cost[i]>0&&sum==0) res=i; // 정답 후보 선정
        sum+=gas[i]-cost[i]; // 합 계산
        if (sum<0) sum=0; // 합이 음수가 되면 다시 0으로 초기화 시켜준다.
    }
    if (total<0) res=-1;
    return res;
}

Solution

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int res, total=0, sum=0;
    for (int i=0;i<gasSize;i++){
        total+=gas[i]-cost[i];
        if (gas[i]-cost[i]>0&&sum==0) res=i;

        sum+=gas[i]-cost[i];
        if (sum<0) sum=0;
    }
    if (total<0) res=-1;
    return res;
}