LeetCode Swift - 134. Gas Station_Greedy

내가 느끼는 전형적인 그리디 문제이다.

주어진 상황을 고려했을때 가장 최선의 선택이 무엇인지 고르는 것.

이 문제도 그렇다. 현재 상황에서 가장 좋은 선택이 어느 idx에서 시작이고 그렇게 출발했다면 그 다음 과정도 성립이 되는가를 확인하고 만약 되지 않는다면 다시 상황을 바꿔서 같은 작업을 반복해주면 된다.

 

이 문제를 풀면서 생각한 논리적 흐름은

1. 먼저 가스와 코스트를 각각 전부 더해본다.
2. 문제 자체가 시계방향으로 한바퀴를 전부 돌아야하기 때문에 Totally Gas가 Cost보다 작다면 문제 자체가 성립되지 않는다.
3. 따라서 이를 먼저 걸러주어 return -1 해준다.
4. 이 과정을 통과했다면 for문과 enumerated를 사용해 idx 별로 gas를 얼마나 축적할 수 있고 i + 1의 목적지까지 사용되는 cost가 얼마인지 확인하여 누적한다.
5. 이 때 만약 currentGas가 currentCost보다 적어지면 위치를 잘못잡았다는 뜻이기에 다시 인덱스 설정을 해주고 currentGas, currentCost 전부 초기화해준다.
6. 이를 반복한다.

 

* 코드

class Solution {
    func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
        let totalGas = gas.reduce(0, +)
        let totalCost = cost.reduce(0, +)
        var ans = 0
        var currentGas = 0
        var currentCost = 0

        if totalGas < totalCost {
            return -1
        }

        for (i, idxGas) in gas.enumerated() {
            let idxCost = cost[i]

            currentGas += idxGas
            currentCost += idxCost

            if currentGas < currentCost {
                ans = i + 1
                currentGas = 0
                currentCost = 0
            }
        }
        return ans
    }
}

 

 

정리(Today I Learned)

1. 전형적인 그리디라는 느낌이 들었다. 리트코드는 영어라서 뭔가 좀 어색하지만... 예시가 명확하게 나와있어 다행이다. 하지만 항상 예시만 보고 문제를 푸는 버릇은 아주 작은 단서들을 무시하고 지나갔다가 나중에 깨닫는 경우를 만들기에... 이를 주의해야겠다.