[LeetCode#134] Gas Station

 

❒ Desciption

---

날짜	2024.09.18 (수)
레벨	Medium
제목	Gas Station
링크	https://leetcode.com/problems/gas-station/description/
자료구조	배열
알고리즘	그리디
시간 복잡도	O(N)

 

문제를 풀이할 때 PriorityQueue와 이중 while 문을 통해 풀이를 하였다.

하지만 이는 굉장히 메모리 측면에서 비효율적인 풀이였다.

 

 

 

 

 

❒ 문제 분석

---

문제에서는 gas 배열과 cost 배열을 input으로 준다.

• int[] gas : 현재 위치에 있는 주요소가 보관하고 있는 gas량
• int[] cost : 해당 위치의 주유소로 이동하기 위해 필요한 gas량

그리고 모든 주유소를 원형으로 연결되어 있다.

문제의 목적은 주어진 gas와 cost 배열을 가지고, 어디서 출발해야 원형으로 전체 주유소를 모두 순회할 수 있는지를

구하는 문제이다.

 

방문여부를 알 수 있는 visited 배열과 현재 위치를 표현해줄 marker가 풀이하는데 필요하다고 생각하고,

다음 주유소로 이동할 수 있다면 marker를 다음 주유소로 이동하고, 방문 여부를 true로 변경해준다.

 

 

 

 

 

❒ Solution

---

1. O(n²) 풀이

public int canCompleteCircuit(int[] gas, int[] cost) {
    //1. 주유소가 1개인 경우 early return
    if (gas.length == 1) {
    	if (gas[0] >= cost[0]) {
            return 0;
        } else {
            return -1;
        }
    }
    
    //2. gas[i] - cost[i] 가 0보다 큰 경우만 시작점으로 선정
    Queue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < gas.length; i++) {
    	if (gas[i] > cost[i]) {
             pq.add(i);
        } 
    }
    
    //3. Main Logic - marker와 visited 배열을 update 하면서 이중 while문 순회
    int answer = -1;
    while (!pq.isEmpty()) {
    	int marker = pq.poll();
        int initial = marker;
        int remaminGas = 0;
        boolean[] visited = new boolean[gas.length];
        
        // 4. 내부 while loop - marker 갱신 및 remainGas 생신
        while (!visited[marker]) {
            
            // 4-1. 현재 marker 방문 처리 후 remainGas 갱신
            visited[marker] = true;
            remainGas += gas[marker] - cost[marker];
            
            // 4-2. gas가 남아있다면 marker 갱신 or break while loop
            if (remainGas >= 0) {
                if (marker >= gas.length - 1) {
                    marker = 0;
                } else {
                    marker ++;
                }
            } else {
            	break;
            }
        }
        // 3-1. 내부 while loop 종료 후, 외부 while loop break 여부 확인
        if (remainGas >= 0) {
            answer = initail;
            break;
        }
    }
    return answer;
}

이 풀이는 알고리즘 공부를 하면서 접한 방식들을 응용해서 풀이했다. 앞선 공부들이 응용이 되어서 다행이지만,

해당 문제를 풀이하는데 있어서는 시간복잡도,메모리 효율 그리고 로직의 가독성이 좋지 않다.

 

 

2. O(n) 풀이 

public int canCompleteCircuit(int[] gas, int[] cost) {
    // 1. 주유소의 모든 gas량과 이동시 필요한 gas량의 차이를 구해, 순환가능 여부 확인.
    if (Arrays.stream(gas).sum() < Arrays.stream(cost).sum()) {
        return -1;
    }
        
    // 2. 현재 위치에서는 주유소를 순회하지 못하는 경우 else 
    int remainGas = 0;
    int start = 0;
    for (int i = 0; i < gas.length; i++) {
        if (remainGas + gas[i] < cost[i]) {
            start = i + 1;
            remainGas = 0;
        } else {
            remainGas += gas[i] - cost[i];
        }
    }
    
    // 3. 결과 반환
    return start;
}

이 풀이는 주유소 순회 가능 여부를 gas 배열의 합과 cost 배열의 합의 차를 구해서 판별한다.

그리고 gas 배열을 순회하면서 해당 index가 시작점이 될 수 있는지 없는지를 판별한다.

시작점이 될 수 있다며 remainGas를 갱신하고, 없다면 시작점을 한 칸 앞으로 이동한다.

 

 

 

 

 

---