Skip to main content

42885. ๊ตฌ๋ช…๋ณดํŠธ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๊ตฌ๋ช…๋ณดํŠธ


๋ฌธ์ œ ์œ ํ˜•๋‚œ์ด๋„๊ฑธ๋ฆฐ ์‹œ๊ฐ„ํ•ด๊ฒฐ ์œ ๋ฌด(โœ…/โŒ)
ํƒ์š•๋ฒ•(๊ทธ๋ฆฌ๋””)lv.21์‹œ๊ฐ„ 30๋ถ„โœ…

์„ค๊ณ„ ๋ฐฉ๋ฒ•#

  • ์‚ฌ๋žŒ๋“ค์„ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ ๋ฌด๊ฑฐ์šด ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.

  • ๋ฌด๊ฑฐ์šด ๋ชธ๋ฌด๊ฒŒ์˜ ์‚ฌ๋žŒ๋ถ€ํ„ฐ

  • ๋ณดํŠธ์˜ย limitย ์—์„œ ๋ชธ๋ฌด๊ฒŒ๋ฅผ ๋บ€ ๋งŒํผ์„ย remainig(๋‚จ์€ ๋ฌด๊ฒŒ)์— ์ €์žฅํ•œ๋‹ค.

  • ๊ฐ€์žฅ ๊ฐ€๋ฒผ์šด ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ย remainingย ๊ณผ ๊ฐ™๊ฑฐ๋‚˜ ์ž‘๋‹ค๋ฉด,

  • ๊ฐ€์žฅ ๊ฐ€๋ฒผ์šด ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ๋งŒํผ์„ย remainig์—์„œ ๋นผ์ค€๋‹ค.

  • ๋ณดํŠธ์—ย remainigย ์„ push ํ•œ๋‹ค.

  • boats์—๋Š” ์‚ฌ๋žŒ์„ ์‹ฃ๊ณ  ๋‚จ์€ ๋ฌด๊ฒŒ๋“ค์ด ์ €์žฅ๋˜์–ด ์žˆ๊ณ , ๊ทธ ๊ธธ์ด๋ฅผ ๋ฆฌํ„ดํ•˜๋ฉด ์ตœ์†Œ ๊ตฌ๋ช…๋ณดํŠธ์˜ ๊ฐœ์ˆ˜์ด๋‹ค.

์ฝ”๋“œ#

function solution(people, limit) {
const boats = [];
people
.sort((a, b) => b - a)
.forEach((heavyPerson) => {
let remaining = limit - heavyPerson;
if (people[people.length - 1] <= remaining) {
remaining -= people.pop();
}
boats.push(remaining);
});
return boats.length;
}

์‹œ๊ฐ„ ๋ณต์žก๋„#

  • sort : O(NlogN)

  • ์ˆœํšŒ : O(N)

  • -> O(NlogN)

์–ด๋ ค์› ๋˜ ์ #

  • ๋ฌธ์ œ๋ฅผ ์ฒ˜์Œ์— ์ œ๋Œ€๋กœ ์ฝ์ง€ ์•Š์•„์„œ, ๋ณดํŠธ์— ์‚ฌ๋žŒ ์ˆ˜ ์ œํ•œ์€ ์—†๊ณ , ๋ฌด๊ฒŒ ์ œํ•œ๋งŒ ์žˆ๋Š” ์ค„ ์•Œ์•˜๋‹ค.

  • ๋ฌธ์ œ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์ฐพ๋Š” ๊ฒƒ์ด ์‰ฝ์ง€ ์•Š์•˜๋‹ค.

  • ์ •๋ ฌ์„ ํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ–ˆ๋Š”๋ฐ, ์ด๋ฅผ ๋– ์˜ฌ๋ฆฌ๊ธฐ ์–ด๋ ค์› ๋‹ค.

  • sort().revers() ๋กœ ์ˆซ์ž๋ฅผ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ๊ธฐ๋Œ€ํ–ˆ๋Š”๋ฐ, sort()๊ฐ€ ์œ ๋‹ˆ์ฝ”๋“œ ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ, [1, 2, 10]์˜ ๊ฒฝ์šฐ [1, 10, 2] ๋กœ ์ •๋ ฌ๋œ๋‹ค๋Š” ๊ฒƒ์„ ์ƒˆ๋กญ๊ฒŒ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค.

์ฐธ๊ณ ์ž๋ฃŒ#

Array.prototype.sort()

Last updated on by WooodHead