(Leet Code JS)Furthest Building You Can Reach

https://leetcode.com/problems/furthest-building-you-can-reach/

Furthest Building You Can Reach - LeetCode

최소힙을 이용한 문제풀이.

벽돌과 사다리를 이용해 가장 멀리 갈 수 있는 빌딩의 인덱스를 리턴하면 된다.

 

pq라는 이름으로 우선순위 큐(최소 힙)을 선언한다.

for문으로 1부터 heights의 길이만큼 순회.

 

현재 빌딩의 높이 - 이전 빌딩의 높이를 구하여 diff에 저장.

만약 diff가 0보다 작거나 같다면 그냥 지나갈 수 있는 높이다.

그렇지 않고 diff가 0보다 크다면 벽돌과 사다리를 이용해 지나간다.

 

우선은 사다리를 이용해 빌딩을 지나간다.

사다리가 남아있다면 pq에 diff를 push하고 사다리의 갯수를 1개 줄인다.

사다리가 남아있지 않다면 pq를 이용해야 한다.

pq의 front가 diff보다 작다면 사다리 대신 벽돌을 이용해 빌딩을 건넌다.

그렇기 때문에 diff를 pq에 넣은 후, 벽돌의 갯수를 diff만큼 줄인다.

 

위 경우에 해당하지 않는 경우 벽돌만 이용해 건넌다.

 

빌딩을 건넌 후 벽돌이 남아있지 않다면 i - 1을 리턴하고,

for문이 끝나게 된다면 모든 빌딩을 건넜기 때문에 length - 1을 리턴한다.

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;
};