💬 문제
가스 충전소가 원형으로 나열되어 있음
각 충전소에서 충전할 수 있는 양의 정수 배열 gas
다음 충전소로 이동하는 데에 필요한 양의 정수 배열 cost
탱크에 가스가 0인채로 출발하고, 한바퀴를 돌 수 있는 시작 인덱스를 반환
순환이 가능한 시작 인덱스는 무조건 하나임
없으면 -1 반환
✍️ 나의 풀이
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function(gas, cost) {
let curr = 0;
let total = 0;
let idx = 0;
for (let i = 0; i < gas.length; i++) {
curr += gas[i] - cost[i];
total += gas[i] - cost[i];
if (curr < 0) {
curr = 0;
idx = i + 1;
}
}
return total < 0 ? -1 : idx;
};curr는 현재 탱크의 가스 양
total은 모든 인덱스의 충전 양 - 소모 양을 합산
인덱스 0부터 시작하여 total에는 계속 쌓고 현재 탱크 내 가스를 계산
만약 < 0 이면 다음으로 이동할 수 없으므로 시작 인덱스로는 불가능
다음으로 넘어가면서 반복하고, 배열을 전부 돌고 났을 때
total이 < 0 이라면 결국에는 모두 돌 수 없는 구조이기 때문에 -1
그게 아니라면 idx 반환
📌 결과
Accepted
Runtime 80ms (Beats 41.89%)
Memory 61.66MB (Beats 61.66%)
📚 러닝 포인트
var canCompleteCircuit = function(gas, cost) {
for (let i = 0; i < gas.length; i++) {
if (gas[i] >= cost[i]) {
let tank = gas[i] - cost[i];
let idx = i === gas.length - 1 ? 0 : i + 1;
while (idx !== i) {
tank = tank + gas[idx] - cost[idx];
if (tank < 0)
break ;
idx = idx === gas.length - 1 ? 0 : idx + 1;
if (idx >= gas.length)
idx = 0;
}
if (idx === i)
return i;
}
}
return -1;
};솔루션을 보기 전에 혼자서 작성했던 코드는 위와 같다. 작성하 서도 이렇게 반복하면 시간이 너무 오래 걸릴 것 같다고 생각했는데 역시나 엄청 긴 테스트 케이스에서 타임 아웃이 났다. 도저히 시작 인덱스를 임시로 지정하고 다시 그 인덱스까지 돌아올 수 있는지 계산하는 방법을 어떻게 줄일 수 있을지 생각이 안나서 오늘도 솔루션을 찾아봤다. 대부분이 설명하기를, 총 gas 값에서 총 cost 값을 뺐을 때 0보다 작다면 방법이 없다고 했다. 오케이 거기까지는 충분히 이해가 갔다. 그런데 그 반대라고 해도 무조건 도착할 수 있는게 보장이 되는가?는 이해가 되지 않았다. When total tank is positive, it means we have enough gas to over all the previous path. 하지만 이런 말을 보았다. 아무래도 구조가 순환이고, 탱크가 용량 제한이 없기 때문에 가능한 방식인 것 같다.
