[LeetCode] 134. Gas Station

https://leetcode.com/problems/gas-station/

Gas Station - LeetCode

Gas Station - Medium

 

주유소가 줄지어 있다.

이 주유소는 동그랗게 연결되어 있고, 인덱스가 오른쪽으로 가는 것은 반시계 방향으로 움직이는 것을 의미한다.

i번째 주유소에서 gas[i]만큼의 기름을 채울 수 있고, 반시계 방향으로 다음 주유소로 가는데 cost[i]만큼의 기름을 사용한다고 할 때,

도중에 기름이 고갈되지 않고 한바퀴를 돌 수 있는지, 돌 수 있다면 몇 번 주유소에서 출발해야 하는지 구하는 문제다.

 

각 주유소에서 채우는 기름과 소비하는 기름에 집중한다.

모든 주유소에서 gas[i] - cost[i] 를 구해주고, 이 값의 합이 0이상이라면 한바퀴 돌 수 있고, 0보다 작다면 불가능하다.

0보다 작으면 바로 -1을 리턴해주자.

0이상이라면 다음 스텝을 진행한다.

 

처음 0번 주유소에서 출발한다고 가정하자. (l=0, r=0)

그 때 기름은

 

1. 처음 기름을 채워 gas[0]

2. 이동하여 gas[0] - cost[0]

 

가 된다.

이 때, gas[0] - cost[0] 가 음수라면, 0번 주유소에서는 출발할 수 없다는 것을 의미하므로,

l 을 1칸 시계방향으로 이동시킨다. (l=0 -> l=gas.size()-1)

gas[0] - cost[0] 가 양수라면, 0번 주유소에서 출발이 가능하므로 반시계방향으로 이동해 다시 살펴보자.

(r=0 -> r=1)

다시 위의 과정을 반복해 gas[i] - cost[i]를 계속더해줘 이것이 음수라면 l을 --, 양수라면 r을 ++ 해주자.

이렇게 해서 l과 r이 다시 만난다면 한 바퀴 돌 수 있다는 것이므로 l을 return해준다.

 

전체 풀이 코드

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int l=0, r=0, sum=0, s=0;
        for (int i=0; i<gas.size(); i++) sum+=gas[i]-cost[i];
        if (sum<0) return -1;
        sum = gas[0]-cost[0];
        while (l!=r || sum<0 || s!=gas.size()) {
            if (sum<0) l = (l-1+gas.size())%gas.size(), sum += gas[l]-cost[l];
            else r = (r+1)%gas.size(), sum += gas[r]-cost[r];
            s++;
        }
        return l;
    }
};