📝LeetCode 134 풀이

---

LeetCode로 ps 공부를 시작한지 한 달쯤 되었다. 아직 10문제? 정도밖에 안 풀어봐서 여전히 어렵다 🤦‍♀️🤦‍♀️🤦‍♀️
난이도가 높은 문제가 아님에도 몇 시간 동안 잡고 있는 경우가 허다하다. 앞으로 조금씩 나아져야 할텐데!! '꾸준함'이 가장 중요한 것 같다. 조급해지지 말고 시간이 걸리더라도 꾸준히 해보자. 파이팅

---

💡문제 정의

Leetcode 134 << 링크
134번 Gas Station은 Greedy 알고리즘을 이용한 문제다.

i번째 gas station에서 얻을 수 있는 gas의 양은 gas[i]에
i번째 gas station에서 i + 1번째 gas station으로 이동하는데에 소요되는 가스의 양은 cost[i]에 있다.

이때 시계방향으로 gas station을 한 바퀴 순회(starting position으로 다시 돌아옴)할 수 있다면, starting gas station의 index를 return / 순회 불가능하다면 -1을 return
만약 한 바퀴 순회 가능한 solution이 존재한다면, 그 solution의 uniqueness는 보장되어 있다.

---

💡풀이

도저히 다른 방법이 생각나지 않아 Brute-force로 복잡하게 풀었더니 Time Limit Exceeded가 떴다. 껄껄

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int tank, index, cnt;

    for (int i = 0;i < gasSize;i++) {
        tank = 0; // 현재 나의 tank에 들어있는 연료 양
        index = i;
        cnt = 0;

        while (cnt < gasSize) {
            tank += gas[index]; // 연료 충전
			
            // 현재 탱크 안의 연료보다 cost가 많다면 break
            if (cost[index] > tank)  
                break;
            
            tank -= cost[index]; // 연료 사용 -> 다음 station으로 이동
            index = (index == gasSize - 1) ? 0 : index + 1 ;
            cnt++;
        }
        
        if (tank >= 0 && cnt == gasSize) {
            return i;
        }
    }

    return -1;
}

계속 고민해보다가 gas[i] - cost[i]를 어떻게든 굴리면 해결할 수 있을 것 같은데... 했지만 결론에 도달하지는 못했다.

이 문제를 해결하기 위해 고려해야 할 주요 사항은 2가지였다.

1. (gas 배열의 sum >= cost 배열의 sum) 이어야 Circuit을 돌 수 있음: cost가 더 많이 든다면 당연히 한 바퀴 순회 불가능
2. 각 지점에 도착할 때 tank에 남아있는 연료의 양('현재' 남아있는 연료의 양)을 고려해야 함

예를 들어 gas와 cost 배열의 size가 7일 때, gas[i] - cost[i]의 값이 위와 같다고 하자. 이 값이 음수라면 해당 지점은 starting position이 될 수 없다. 따라서 ans를 다음 인덱스 값으로 설정한다. 또한 이 값이 음수라면 curSum을 0으로 reset 해주어야 한다! 바로 이 부분에서 Greedy 알고리즘이 사용되는 것.

코드는 아래와 같다.

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
    int curSum = 0, realSum = 0, ans = 0;

    for (int i = 0;i < gasSize;i++) {
        curSum += gas[i] - cost[i];
        realSum += gas[i] - cost[i];

        if (curSum < 0) {
            ans = i + 1;
            curSum = 0;
        }
    }
    return (realSum < 0) ? -1 : ans;
}

---

💡참고

https://www.youtube.com/watch?v=lJwbPZGo05A
https://ifuwanna.tistory.com/361