Portfolio

📄문제

✏️풀이

재영

첫 번째 풀이

꽤나 많은 연산을 필요로 해서 불만이었어오.


const canCompleteCircuit = (gas, cost) => {
  const total = gas.map((g, i) => g - cost[i]);
  const totalLength = total.length;
  let i = 0;
  while (i < totalLength) {
    let cnt = total[i];
    let flag = true;
    for (let j = 0; j < totalLength; j += 1) {
      const idx = ((i + j) % totalLength);
      const nextIdx = ((idx + 1) % totalLength);
      if (cnt < 0 || cnt + total[nextIdx] < 0) {
        flag = false;
        break;
      };
      cnt += total[nextIdx];
    }
    if (flag && cnt >= 0) return i;
    i += 1;
  }
  return -1
}

두 번째 방법

해봤는데, 굳이 이후의 값을 비교하나 싶었어오.

현재 + 이후의 값 = 과거 + 현재의 값과 같기 때문이었어요. (점화식)

따라서, 이를 다 쳐내고, 현재의 값 < 지금까지의 합을 비교하고, 아니면 그냥 다음으로 넘어가서 확인하는 방식으로 했어요.

이때, 맨 처음 체크할 때 총 합이 -1가 아닌 이상, 이 문제는 답이 있게 되어 있읍니다.

(왜냐! 답은 고유의 값만 허용하며, 총 합이 0만 안넘어가면 어찌어찌 다 돌게 되더라구요.)

따라서 이대로 풀어 보니, O(N)까지는 나오는 군유.


const canCompleteCircuit = (gas, cost) => {
  const total = gas.map((g, i) => g - cost[i]);
  if (total.reduce((acc, cur) => acc + cur, 0) < 0) return -1;
  let lastIdx = 0;
  let cnt = 0;
  total.forEach((val, idx) => {
    if (cnt + val < 0) {
      cnt = 0;
      lastIdx = idx + 1;
      return;
    }
    cnt += val;
  })
  return lastIdx;
}

효성


var canCompleteCircuit = function (gas, cost) {
    let start = 0, tank = 0, total = 0;
    
    for(let i=0; i<gas.length; i++) {
        const consume = gas[i] - cost[i];
        tank += consume;
        
        if(tank < 0) {
            tank = 0;
            start = i + 1;
        }
        
        total += consume;
    }
    
    return total < 0 ? -1 : start;
};

은찬


const checkCircuit = (goal, remainingGas, length) => {
    let goingIndex = goal + 1;
    let currentGas = remainingGas[goal];
    
    if(goingIndex === length){
        goingIndex = 0;
    }
    
    while(goingIndex !== goal){
        currentGas += remainingGas[goingIndex++];
        
        if(currentGas < 0){
            return false;
        }
        
        if(goingIndex === length){
            goingIndex = 0;
        }
    }
    
    return true;
}

const canCompleteCircuit = (gas, cost) => {
    const length = gas.length;
    const remainingGas = Array(length + 1).fill(0);
    const startIndex = [];
    let minusGas = 0;
    let plusGas = 0;
    
    
    for(let i = 0; i < length; i++){
        remainingGas[i] = gas[i] - cost[i];
        
        if(remainingGas[i] >= 0){
            startIndex.push(i);
            plusGas += remainingGas[i];
        } else{
            minusGas += remainingGas[i];
        }
    }
    
    if(plusGas + minusGas < 0){
        return -1;
    }
    
    for(let i = 0; i < startIndex.length; i++){
        if(checkCircuit(startIndex[i], remainingGas, length)){
            return startIndex[i];
        }
    }
    
    return -1;
};

현석


var canCompleteCircuit = function(gas, cost) {
    const gasCycle = [...gas, ...gas]
    const costCycle = [...cost, ...cost]
    let startIdx = -1;
    
    for (let i = 0; i < gas.length; i++) {
        if (gas[i] < cost[i]) continue;
        
        let acc = 0;
        
        for (let j = i; j < i + gas.length; j++) {
            acc += gasCycle[j]
            acc -= costCycle[j]
            
            if (acc < 0) break;
        }
        if (acc >= 0 ) {
            startIdx = i
            break;
        } 
    }
    return startIdx
};

가영


var canCompleteCircuit = function(gas, cost) {
    const arr = gas.map((elt, idx) => [elt, idx])
                    .filter((elt, idx) => elt[0] >= cost[idx]);
    
    for (const a of arr) {
        const startIdx = a[1];
        let total = a[0] - cost[startIdx];
        let nextIdx = startIdx === cost.length - 1 ? 0 : startIdx + 1;
        
        while (total >= 0) {
            if (nextIdx === startIdx) return startIdx;

            total += (gas[nextIdx] - cost[nextIdx]);
            
            nextIdx = nextIdx + 1 < cost.length ? nextIdx + 1 : 0;
        }
    }
  
    return -1;
};

Gas Station

📄문제

✏️풀이