❒ 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를 갱신하고, 없다면 시작점을 한 칸 앞으로 이동한다.
'Algorithm > 문제풀이' 카테고리의 다른 글
[LeetCode#687] Longest Univalue Path (0) | 2024.09.21 |
---|---|
[LeetCode#455] Assign Cookies (0) | 2024.09.19 |
[LeetCode#621] Task Scheduler (0) | 2024.09.17 |
[LeetCode#406] Queue reconstruction by height (0) | 2024.09.17 |
[LeetCode#122] Best Time to Buy and Sell II (0) | 2024.09.16 |