1642. Furthest Building You Can Reach
2024년 2월 17일 작성
LeetcodeGreedyPriority Queue
저번에 CTCI 읽으면서 일단, 알고리즘 풀때 인간이 문제를 푸는 방식으로 생각해보라고 해서 문제 읽자마자 그냥 떠오르는 방법으로 써봤다.
import java.lang.Math;
class Solution {
private int[] h;
private int buildingCnt;
public int furthestBuilding(int[] heights, int bricks, int ladders) {
h = heights;
buildingCnt = heights.length;
return rec(0, bricks, ladders);
}
private int rec(int i, int bricks, int ladders) {
if (i == buildingCnt-1) {
return 0;
}
int diff = h[i+1] - h[i];
if (diff <= 0) {
return 1 + rec(i+1, bricks, ladders);
}
int byLadder = ladders > 0 ? rec(i+1, bricks, ladders - 1) + 1 : 0;
int byBricks = bricks - diff >= 0 ? hi(i+1, bricks-diff, ladders) + 1 : 0;
return Math.max(byLadder, byBricks);
}
}테스트케이스는 모두 통과해서 제출해봤더니,
11/78 개의 문제만 통과하고 Time Limit Exceeded가 떴다.
한 십분 생각했는데 방법이 아예 생각도 안나서 지피티에게 힌트를 달라고 했더니
Priority Queue를 사용해보라고 했다. 물어보지도 않았는데 정답 코드를 줘서 당황했지만
이해에는 도움이 되었다; (그래도 양심껏 코드는 베끼지 않았다.)
코드를 보니, 우선순위큐를 사용하는 이유가 사다리를 쓸지, 벽돌을 쓸지 선택하는 것을 미루기 위해서였다.
위에 내 코드를 보면, 내가 생각한 방법은 빌딩을 건너가는 순간마다 항상 둘 중 하나를 선택해야만 한다는 전제가 있음을 알 수 있는데
이 전제 없이 문제를 풀 수 있는 방법인 것이다.
일단 사다리 갯수만큼 우선순위 큐에 차곡차곡 점프해야하는 높이들을 넣어준다.
그렇게 사다리 갯수보다 많아졌을 때, 그 때 가장 낮은 높이를 큐에서 빼고 그만큼 벽돌을 쓰면 된다.
벽돌이 동날 때까지 그렇게 하면 가장 최적의 선택을, 계산 몇번 하지 않고 할 수 있는 것이다 :D
import java.util.PriorityQueue;
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < heights.length - 1; i++) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
priorityQueue.add(diff);
}
if (priorityQueue.size() > ladders) {
int minDiff = priorityQueue.poll();
bricks -= minDiff;
if (bricks < 0) {
return i;
}
}
}
return heights.length - 1;
}
}시간복잡도 계산하기:
빌딩의 갯수를 N이라고 하면 for문을 n번 반복한다.
그리고 그 때마다 queue add 연산을 하고, 필요한경우 poll 연산도 한다.
for문 안은 2 * O(log N) 이므로 전체는 O(N logN) 일 것 같다.
gpt한테 답 확인하기
