[Greedy/우선순위 큐] 1642. Furthest Building You Can Reach

문제 바로가기

Furthest Building You Can Reach - LeetCode

 

미디엄 문제긴 한데 꽤 간단합니다. 빌딩을 타 넘어야 되는데요, 벽돌과 사다리의 개수를 고려해서 최대한 많이 타 넘어가야 합니다. 우선순위 큐를 써서 최적의 답을 찾으면 됩니다.

 

class Solution {
  public int furthestBuilding(int[] heights, int bricks, int ladders) {
    // 빌딩 높이 차이를 저장
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    
    for (int i = 0; i < heights.length - 1; i++) {
      int diff = heights[i + 1] - heights[i];
      if (diff <= 0) {
        continue;
      }
      
      pq.offer(diff);
      if (pq.size() > ladders) {
        bricks -= pq.poll();
      }
      
      if (bricks < 0) {
        return i;
      }
    }
    
    return heights.length - 1;
  }
}

 

아이디어는 다음과 같습니다.

 

우선 PQ 에는 빌딩 높이의 차이(diff) 를 저장합니다. 그리고 사다리를 사용할 수 없을 때 pq의 루트 노드만큼의 벽돌 개수를 사용하고 빌딩을 넘어가는 겁니다.

 

pq의 크기가 사다리의 개수보다 큰 경우가 바로 사다리를 사용할 수 없을 때입니다. PQ의 크기가 타 넘어가야 하는 빌딩의 수와 같기 때문이죠. 이 경우 벽돌을 써버리고, 만약 벽돌의 개수가 0보다 작아진다면 더 이상 다음 빌딩으로 넘어갈 수 없기 때문에 반복문을 종료하면 됩니다.

 

 

처음에는 사다리의 개수도 마이너스를 해가면서 반복문을 돌려야 하나 생각했는데, 그럴 필요가 없습니다. PQ의 원소의 개수만큼 사다리를 사용하면 되니깐요 ^_^.

 

 

 

다음엔 좀 더 여러운 문제를 도전해봐야겠습니다.

그럼 20000