[C] LeetCode 134. Gas Station

 

문제 (원문)

문제(번역)

n개의 주유소가 원형 길을 따라 있다. i 번째 주요소에서의 가스 양은 gas[i]이다.

무한대의 가스 탱크를 가진 차가 있고, i번째 주유소에서 i+1번째 주유소로 가는 가스 비용은 cost[i]이다. 

아무 주유소에서부터 빈 탱크로 여정을 시작해야 한다.

gas와 cost 두 정수 배열이 주어졌을 때 시계방향으로 여행을 갈 수 있는 주유소의 인덱스를 반환해라.

해답이 있다면 그 해답이 유일하다는 것이 보장된다.

접근 방법

처음에는 단순하게 생각했다.

gas[i]-cost[i]를 한 값이 0보다 크거나 같은 위치를 먼저 모은 다음,

각 위치에서부터 시계방향으로 순회하여 자기 자신까지 도착할때까지 가스 탱크가 음수가 되지 않는지 검사했다.

이렇게 풀이하는 경우 시간 초과가 발생한다.

 

내가 i번째 주유소에 갔을때 얻을 수 있는 실질적인 가스는 gas[i] - cost[i]이다.

또한 이 값 자체는 일시적으로 음수가 될 수 있지만 실질적으로 얻는 가스의 합이 음수가 되는 순간 해당 경로는 포기해야 한다.

 

즉 우리가 확인해야 하는 부분은 다음과 같다.

1. 실질적으로 얻는 가스의 합이 0이면 해당 케이스는 절대 불가능하다.

2. 특정 구간에서의 가스의 합이 0이면 그 구간에서는 출발할 수 없다.

 

이 아이디어를 바탕으로 아래처럼 코드를 작성했다.

소스코드

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
    int sum=0, diff = 0, start= 0;
    for(int i=0; i<gasSize; i++) {
        sum += (gas[i] - cost[i]);
        diff += (gas[i] - cost[i]);
        if(diff < 0) {
            diff = 0;
            start = i+1;
        }
    }
    if(sum< 0) return -1;
    return start;
}

 

이렇게 하면 시간복잡도 O(n) , 공간복잡도 O(1) 로 문제를 해결할 수 있다.

 

근데 이렇게 풀어도 여전히 메모리 사용량에서는 좀 밀린다..