๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/LeetCode

[LeetCode] Furthest Building You Can Reach

๋ฌธ์ œ๋งํฌ

 

Furthest Building You Can Reach - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

์ฃผ์–ด์ง„ ๋ฒฝ๋Œ๊ณผ ๋ฐง์ค„์„ ์ด์šฉํ•˜์—ฌ ์ตœ๋Œ€ํ•œ ๊ฑด๋„ ์ˆ˜ ์žˆ๋Š” ๋นŒ๋”ฉ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.

์กฐ๊ฑด 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
};

'์ฝ”๋”ฉํ…Œ์ŠคํŠธ > LeetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[LeetCode] 3Sum Closest  (0) 2022.06.23
[LeetCode] 3Sum  (0) 2022.06.23
[LeetCode] search-suggestions-system  (0) 2022.06.19
[LeetCode] Zigzag Conversion  (0) 2022.06.17
[LeetCode] Longest Substring without Repeating Characters  (0) 2022.06.17