forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjdy8739.js
More file actions
50 lines (39 loc) ยท 1.31 KB
/
jdy8739.js
File metadata and controls
50 lines (39 loc) ยท 1.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
const arr = [0];
for (let i = 1; i <= n; i++) {
const num = binary(i);
arr.push(num);
}
return arr;
};
/** ์ฑ๋ฅ์ด ๋๋ฆฌ์ง๋ง ๊ฐ๊ฒฐํ ํจ์ */
function binary(n) {
return n.toString(2).split('').filter((el) => el === '1').length;
}
// ์๊ฐ๋ณต์ก๋ O(n2) -> n์ ์ด์ง์๋ฌธ์์ด๋ก ๋ณํํ๊ณ ์ด๋ฅผ ๋ฒผ์ดํํ์ฌ 1์ธ ์์๋ง ํํฐ๋งํ๊ณ ๊ทธ ๊ฒฐ๊ณผ์ ๊ธธ์ด๋ฅผ ๊ตฌํ๋ค.
// ์ฌ๊ธฐ์ filter๋ฅผ ์ฌ์ฉํ์ฌ ๋ฐฐ์ด์ ํ ๋ฒ ์ํํ๊ธฐ ๋๋ฌธ์ for๋ฌธ๊ณผ ์ค์ฒฉ๋์ด 2์ค ๋ฃจํ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง
/** ์ฑ๋ฅ์ด ๋น ๋ฅด์ง๋ง ๋ณต์กํ ํจ์ */
function binary(n) {
let num = 1;
let count = 0;
while (num * 2 <= n) {
num = num * 2;
}
while (0 <= n) {
if (num <= n) {
n = n - num;
count++;
}
if (num === 1) {
break;
}
num = num / 2;
}
return count;
}
// ์๊ฐ๋ณต์ก๋ O(n2) -> for๋ฌธ ์์ while๋ฌธ์ด ๋๋ฉด์ i๊ฐ ์ด์ง์๋ก ๋ณํ๋ ๊ฒฝ์ฐ 1์ด ๋ช๊ฐ์ธ์ง ๋ฐํํ๊ธฐ ๋๋ฌธ์ 2์ค ๋ฃจํ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง
// ๊ณต๊ฐ๋ณต์ก๋ O(n) -> for๋ฌธ์ ๋๋ฉด์ arr์ i๊ฐ ์ด์ง์๋ก ๋ณํ๋ ๊ฒฝ์ฐ 1์ด ๋ช ๊ฐ์ธ์ง ์์๋ก ์ถ๊ฐํจ