(LeetCode) 134. Gas Station

The link : leetcode.com/problems/gas-station/

Gas Station - LeetCode

문제 풀이는 다음과 같다. 

 

1. 정답으로 출력할 출발 위치인 index, 출발 위치에 따라 변하는 가스의 충전값 indexsum, 전체 가스 충전값을 구할 totalsum 3가지 변수를 세운다.

2. for문을 gas의 size만큼 돌린다.

3. indexsum의 값은 indexsum += gas[i] - cost[i]이다. 즉, i번째 가스를 충천하고 동시에 i번째 위치까지 가는데 필요한 가스를 제거한다.

4. totalsum의 값은 3번과 동일하다. 

5. 이때, indexsum의 값이 음수로 계산되면 index는 i+1로 지정해주고 indexsum은 0으로 초기화한다. 즉, index의 위치에서 시작하면 가스가 바닥나서 다음지점으로 갈 수 없다는 것을 뜻한다. 때문에 index를 다음칸으로 옮겨주고 indexsum또한 초기화해준다.

6. 정답의 출력 조건은 totalsum이 0 이상이냐 아니냐 이다. 만약 totalsum이 음수라면 어떤 지점에서 출발해도 가스가 동날 수 밖에 없다는 의미이므로 정답으로 -1을 출력한다. 그렇지 않을 경우 index를 답으로 출력한다.

 

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int indexsum = 0, totalsum = 0, index = 0;
        for(int i=0; i<gas.size(); i++){
            indexsum += gas[i] - cost[i];
            totalsum += gas[i] - cost[i];
            if(indexsum<0){
                index = i+1;
                indexsum = 0;
            }
        }
        return totalsum < 0 ? -1 : index;
    }
};

 

그리디는 볼때마다 어렵다. 보통 한 번에 못풀고 다른이의 답을 참고해야지 쉽게 풀 수 있다.