[LeetCode] Furthest Building You Can Reach

문제링크

Furthest Building You Can Reach - LeetCode

주어진 벽돌과 밧줄을 이용하여 최대한 건널 수 있는 빌딩의 수를 구하는 문제이다.

조건 1. 현재 빌딩의 높이가 다음 빌딩의 높이보다 크거나 같을때 ladders와 bricks를 사용하지 않고 건널 수 있다.
조건 2. 현재 빌딩의 높이가 다음 빌딩보다 작을때 ladder을 사용하거나 bricks을 사용해 건널 수 있다.
            (ladder은 다음 빌딩과 현재 빌딩의 높이 차가 얼마나 크던 상관없이 건널 수 있게 한다.)
            (bricks는 1개당 높이 1로 취급하여 현재 빌딩과 다음 빌딩의 차이만큼 사용하여 건널 수 있다.)

주의점 : ladder을 사용하는 것이 이득인지 bricks를 사용하는 것이 이득인지 판단하여 사용해야 한다.
 
빌딩의 높이가 담긴 배열 : heights
주어진 벽돌의 수 : bricks
주어진 밧줄의 수 : ladders

접근 방법

우선 각 빌딩의 현재 위치에서 다음 빌딩으로 건너는 데 필요한 벽돌의 수를 배열로 만들었다. ( 다음 빌딩이 더 낮을 땐 0으로 표현)

let needBricks = new Array(buildingLen).fill(0);
    
for(let idx = 1; idx < buildingLen; idx++){
    needBricks[idx] = Math.max(0, heights[idx] - heights[idx - 1])
}​

그리고 중간까지 갈 수 있는지 이진 탐색법을 통해 탐색하였다.

while (left < right){
    const mid = Math.ceil((left + right) / 2)
    if(canReach(mid)){
        left = mid
    }else{
        right = mid - 1;
    }
}​

canReach 메서드는 매개변수로 주어진 index까지 도달할 수 있으면 true, 도달할 수 없으면 false를 반환한다.

const canReach = (buildingIdx) => {
    if(ladders > buildingIdx) return true;

    const bricksArr = needBricks.slice(0, buildingIdx + 1).sort((a, b) => a - b);

    let bricksCnt = bricks;
    let idx = 0;
    while(bricksCnt >= 0 && idx < bricksArr.length - ladders){
        bricksCnt -= bricksArr[idx];
        idx += 1;
    }
    return bricksCnt >= 0;
}​

만약 밧줄이 주어진 building index보다 크다면 모두 밧줄을 사용하여 건널 수 있으므로 true를 반환한다.

그게 아니라면 앞서 건너기 위한 벽돌의 수를 저장한 needBricks 배열의 building index까지 잘라 오름차순으로 정렬한 배열을 bricksArr에 저장한다.
( 이렇게 오름차순으로 정렬하고 ladders의 크기만큼 뺀다면 가장 Gap이 큰 빌딩들은 빠지게 되므로 나머지는 벽돌만을 이용해 건널 수 있게 된다.)

마지막으로 남은 벽돌의 수가 0보다 크고, index가 bricksArr.length - ladders를 만족할때까지 조건문을 돌리고
남은 벽돌의 수가 0보다 크거나 같으면 true, 작으면 false를 반환한다.

/**
 * @param {number[]} heights
 * @param {number} bricks
 * @param {number} ladders
 * @return {number}
 */
var furthestBuilding = function(heights, bricks, ladders) {
    let buildingLen = heights.length;
    let left = 0, right = buildingLen - 1;
    
    let needBricks = new Array(buildingLen).fill(0);
    
    for(let idx = 1; idx < buildingLen; idx++){
        needBricks[idx] = Math.max(0, heights[idx] - heights[idx - 1])
    }
    
    const canReach = (buildingIdx) => {
        if(ladders > buildingIdx) return true;
        
        const bricksArr = needBricks.slice(0, buildingIdx + 1).sort((a, b) => a - b);
        
        let bricksCnt = bricks;
        let idx = 0;
        while(bricksCnt >= 0 && idx < bricksArr.length - ladders){
            bricksCnt -= bricksArr[idx];
            idx += 1;
        }
        return bricksCnt >= 0;
    }
    
    while (left < right){
        const mid = Math.ceil((left + right) / 2)
        if(canReach(mid)){
            left = mid
        }else{
            right = mid - 1;
        }
    }
    
    return left
};