Skip to main content

43165. ํƒ€๊ฒŸ ๋„˜๋ฒ„

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ํƒ€๊ฒŸ ๋„˜๋ฒ„


๋ฌธ์ œ ์œ ํ˜•๋‚œ์ด๋„๊ฑธ๋ฆฐ ์‹œ๊ฐ„ํ•ด๊ฒฐ ์œ ๋ฌด(โœ…/โŒ)
BFS/DFSlv.230๋ถ„โœ…

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

  • ์ˆซ์ž ๋ฐฐ์—ด๊ณผ ํƒ€๊ฒŸ์„ bfs ํ•จ์ˆ˜์— ๊ทธ๋Œ€๋กœ ๋„˜๊ธฐ๊ณ , ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ๋ฆฌํ„ดํ•œ๋‹ค.

  • bfs ํ•จ์ˆ˜๋Š”, ๋ฐ›์€ ์ˆซ์ž ๋ฐฐ์—ด์˜ ๋ณต์‚ฌ๋ณธ์„ ๋งŒ๋“ค๊ณ  (pop ์—ฐ์‚ฐ์ด ์ฐธ์กฐํ•œ array๋ฅผ ๋ชจ๋‘ ๋ณ€๊ฒฝํ•˜๊ธฐ ๋•Œ๋ฌธ์—)

  • ๋ณต์‚ฌ๋ณธ์—์„œ ๋งˆ์ง€๋ง‰ ์ˆซ์ž๋ฅผ ์ œ๊ฑฐํ•˜๊ณ ,

  • ๋งˆ์ง€๋ง‰ ์ˆซ์ž๊ฐ€ ์ œ๊ฑฐ๋œ ๋ฐฐ์—ด๊ณผ ๋งˆ์ง€๋ง‰ ์ˆซ์ž๋ฅผ ํƒ€๊ฒŸ ๋„˜๋ฒ„์— +, - ์—ฐ์‚ฐ์„ ํ•œ ๊ฒฐ๊ณผ๋ฅผ ํƒ€๊ฒŸ ๋„˜๋ฒ„๋กœ bfs ํ•จ์ˆ˜์— ๊ฐ๊ฐ ๋ณด๋‚ด๊ณ  ๊ฒฐ๊ณผ๋ฅผ ๋ฆฌํ„ด ๋ฐ›๋Š”๋‹ค.

  • bfs ํ•จ์ˆ˜๋Š” ์ˆซ์ž ๋ฐฐ์—ด์˜ ๊ธธ์ด๊ฐ€ 1์ผ ๋•Œ, ๋‚จ์€ ์ˆซ์ž๊ฐ€ ํƒ€๊ฒŸ ๋„˜๋ฒ„ ๋˜๋Š” - ํƒ€๊ฒŸ ๋„˜๋ฒ„์™€ ๊ฐ™๋‹ค๋ฉด 1์„ ๋ฆฌํ„ดํ•œ๋‹ค.

์ฝ”๋“œ#

  • 1์ฐจ ํ’€์ด
function solution(numbers, target) {
return bfs(numbers, target);
}
function bfs(numbers, target) {
const clone = [...numbers];
if (clone.length === 1) {
return Number(clone[0] === target || clone[0] === -target);
}
const lastNumber = clone.pop();
return bfs(clone, target - lastNumber) + bfs(clone, target + lastNumber);
}
  • 2์ฐจ ํ’€์ด

โ˜ ๋‹ค์‹œ ๋ณด๋‹ˆ ์ด๊ฑด ๋จผ์ € ์‹คํ–‰ํ•˜๋Š” ํ•จ์ˆ˜๋ถ€ํ„ฐ ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ํ•˜๊ธฐ ๋•Œ๋ฌธ์— dfs ์˜€๋‹ค. ๊ทธ๋ฆฌ๊ณ  numbers.length === 0 ์ผ ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜๋Š” ๊ฒƒ์ด ์ฝ”๋“œ ๊ฐ€๋…์„ฑ์ด ๋†’์•˜๋‹ค. ๋ฐฐ์—ด์€ ์ฐธ์กฐํ˜•์ด๊ธฐ ๋•Œ๋ฌธ์— ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ๋ฐ›์€ ๋ฐฐ์—ด์„ pop ํ•˜๋ฉด ์›๋ณธ ๋ฐฐ์—ด๋„ ๋ณ€ํ•˜๋ฏ€๋กœ ๋ณต์‚ฌ๋ณธ์„ ๋„˜๊ฒจ์ฃผ์—ˆ๋‹ค.

function solution(numbers, target) {
return dfs(numbers, target);
}
function dfs(numbers, target) {
if (!numbers.length) {
return target === 0 ? 1 : 0;
}
const lastNumber = numbers.pop();
return (
dfs([...numbers], target - lastNumber) +
dfs([...numbers], target + lastNumber)
);
}

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

  • O(2^N)

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

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

  • ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๊ฐ€ 1๊ฐœ์—ฌ์„œ ํž˜๋“ค์—ˆ๋‹ค.

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

Last updated on by WooodHead