Daily LeetCode Challenge - 134. Gas Station

Problem From.

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

오늘 문제는 gas 와 cost 배열이 주어졌을때, gas 배열의 특정 인덱스에서부터 시작하여 다시 그 인덱스로 돌아올 수 있는지 보는 문제였다.

gas 배열의 해당 인덱스만큼 tank 에 gas 를 충전하고 다음 gas station 으로 가는데에 cost 만큼이 빠져나가는 방식인데 문제의 제한사항에 정답이 단 하나 있는것이 보장되어 있다는 제한 사항이 있었다.

그 제한사항을 활용하여, gas 배열을 순회하면서 tank += gas[i] - cost[i] 를 하면서 tank 가 음수가 되면 인덱스를 초기화 해주고 아니라면 계속 진행해주는 방식으로 풀었다.
또한 total 도 배열 순회시에 계속 주시하면서 마지막에 total 이 음수라면 -1 을 반환해주었다.

class Solution {
    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        
        var total = 0
        var tank = 0
        var index = 0
        
        for(i in 0 until gas.size) {
            
            total += gas[i] - cost[i]
            tank += gas[i] - cost[i]
            
            if(tank < 0) {
                tank = 0
                index = i + 1
            }
        
        }
        
        return if(total < 0) -1 else index
        
    }
}

위 문제의 시간 복잡도는 O(n) 이 된다.