Gas Station

[hsskey]

문제 설명 | Gas Station

📝 제약조건

• n == gas.length == cost.length
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4

💡 예시

• Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

  • Output: 3

• Input: gas = [2,3,4], cost = [3,4,3]

  • Output: -1

문제 해결 과정

Step 1: 문제 이해하기

• 주유소를 순환하면서 여행을 완료할 수 있는 시작점을 찾아야 함.
• 차량은 항상 빈 탱크로 시작.
• 각 주유소에서 가스를 충전하고, 다음 주유소로 이동하는 데 가스를 소모.
• 예시로 직접 확인해보기:
  • 예시 1: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
    • 인덱스 3에서 시작했을 때 순환 가능
  • 예시 2: gas = [2,3,4], cost = [3,4,3]
    • 어디서 시작해도 순환 불가능

Step 2: 접근 방법

• 직관적으로 생각하기

  • 전체 가스 양이 전체 비용보다 작으면 불가능
  • 가능한 모든 시작점을 고려해야 함

• 관찰할 중요한 패턴

  • 만약 i에서 j까지 가는 것이 불가능하다면, i와 j 사이의 어떤 지점에서 시작해도 j에 도달할 수 없음
  • 따라서 가스가 부족해지는 지점 다음부터 새롭게 시작하면 됨

Step 3: 코드 설계

1. 총 가스량과 총 비용을 비교하여 해결 가능성 확인
2. 가능한 시작점 찾기:
   • 각 지점에서 남은 가스량 계산 (gas[i] - cost[i])
   • 가스가 부족해지면(음수) 시작점을 다음 지점으로 갱신
   • 마지막까지 돌았을 때 남은 시작점이 정답

Step 4: 코드 구현

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    // 총 가스량과 총 비용 계산
    let totalGas = 0;
    let totalCost = 0;
    for (let i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
    }
    
    // 총 가스량이 총 비용보다 작으면 불가능
    if (totalGas < totalCost) return -1;
    
    // 가능한 시작점 찾기
    let tank = 0;
    let start = 0;
    
    for (let i = 0; i < gas.length; i++) {
        tank += gas[i] - cost[i];
        
        // 현재 지점까지 가스가 부족하면 다음 지점에서 시작
        if (tank < 0) {
            tank = 0;
            start = i + 1;
        }
    }
    
    return start;
};