๋ฌธ์ ๋งํฌ
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 |