Portfolio

문제

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.

If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Example 1:


Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:


Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:


Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Constraints:

1 <= heights.length <= 105

1 <= heights[i] <= 106

0 <= bricks <= 109

0 <= ladders <= heights.length

풀이

재영


class MinHeap {
  constructor() {
    this.heap = [null];
    this.size = 0;
  }
  heappush(value) {
    this.heap.push(value);
    let nowIndex = this.heap.length - 1;
    let parentIndex = Math.floor(nowIndex / 2);
    while (nowIndex > 1 && this.heap[parentIndex] > this.heap[nowIndex]) {
      this.swap(nowIndex, parentIndex);
      nowIndex = parentIndex;
      parentIndex = Math.floor(nowIndex / 2);
    }
    this.size += 1;
  }
  heappop() {
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();
    let nowIndex = 1;
    let leftIndex = nowIndex * 2;
    let rightIndex = nowIndex * 2 + 1;
    while (
      this.heap[nowIndex] > this.heap[leftIndex] ||
      this.heap[nowIndex] > this.heap[rightIndex]
    ) {
      if (this.heap[rightIndex] < this.heap[leftIndex]) {
        this.swap(nowIndex, rightIndex);
        nowIndex = rightIndex;
      } else {
        this.swap(nowIndex, leftIndex);
        nowIndex = leftIndex;
      }
      leftIndex = nowIndex * 2;
      rightIndex = nowIndex * 2 + 1;
    }
    this.size -= 1;
    return returnValue;
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
}

var furthestBuilding = function (heights, bricks, ladders) {
  const arr = new MinHeap();
  let prev = heights[0];
  let cnt = 0;
  for (let i = 1; i < heights.length; i += 1) {
    const now = heights[i];

    if (now > prev) {
      arr.heappush(now - prev);

      if (ladders) {
        ladders -= 1;
      } else {
        bricks -= arr.heappop();
      }
    }

    if (bricks < 0) return cnt;

    prev = heights[i];
    cnt += 1;
  }

  return cnt;
};

은찬


class PriorityQueue {
    constructor(){
        this.queue = [0];
        this.size = 0;
    }
    
    moveUp(index){
        while(Math.floor(index / 2)){
            const parent = Math.floor(index / 2);
            
            if(this.queue[parent] > this.queue[index]){
                [this.queue[parent], this.queue[index]] = [this.queue[index], this.queue[parent]];
            }
            
            index = parent;
        }
    }
    
    moveDown(index){
        while(index * 2 <= this.size){
            const minChildIndex = this.findMinChildIndex(index);
            
            if(this.queue[index] > this.queue[minChildIndex]){
                const tmp = this.queue[minChildIndex];
                
                this.queue[minChildIndex] = this.queue[index];
                this.queue[index] = tmp;
            }
            
            index = minChildIndex;
        }
    }
    
    findMinChildIndex(index){
        const left = index * 2;
        const right = (index * 2) + 1;
        
        if(right > this.size){
            return left;
        } else{
            if(this.queue[right] < this.queue[left]){
                return right;
            } else{
                return left;
            }
        }
    }
    
    push(value){
        this.queue.push(value);
        this.size++;
        
        this.moveUp(this.size);
    }
    
    
    pop(){
        const minValue = this.queue[1];
        
        this.queue[1] = this.queue[this.size];
        this.queue.pop();
        this.size--;
        this.moveDown(1);
        
        return minValue;
    }
    
    front(){
        return this.queue[1];
    }
}

const furthestBuilding = (heights, bricks, ladders) => {
    const { length } = heights;
    const pq = new PriorityQueue();
    
    for(let i = 1; i < length; i++){
        const diff = heights[i] - heights[i - 1];
        
        if(diff > 0){
            if(ladders){
                pq.push(diff);
                ladders--;
            } else if(pq.front() && diff > pq.front()){
                pq.push(diff);
                bricks -= pq.pop();
            } else{
                bricks -= diff;
            }
        }
        
        if(bricks < 0){
            return i - 1;
        }
    }
    
    return length - 1;
};

Furthest Building You Can Reach

문제

풀이