알고리즘
[Swift] LeetCode - 134. Gas Station
고고
2022. 2. 28. 14:32
문제: https://leetcode.com/problems/gas-station/
Gas Station - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
전체 기름의 양 < 전체 비용일 경우 반드시 모든 주유소를 방문할 수 있습니다.
O(n)으로 돌며 성립되지 않는 지점이 있다면 출발점을 그 다음 지점으로 갱신합니다.
import Foundation
class Solution {
func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
if gas.reduce(0, +) < cost.reduce(0, +) {
return -1
}
var start = 0, fuel = 0
for i in 0..<gas.count {
if gas[i] + fuel < cost[i] {
start = i + 1
fuel = 0
} else {
fuel += gas[i] - cost[i]
}
}
return start
}
}
print(Solution().canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])) // 3
print(Solution().canCompleteCircuit([2,3,4], [3,4,3])) // -1