๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - 2๊ฐ ์ดํ๋ก ๋ค๋ฅธ ๋นํธ
programmers.co.kr
์ ๊ทผ ๋ฐฉ๋ฒ
์ฒ์์๋ ๋ binary ๋ฌธ์์ด์ ๋น๊ตํ์ฌ 1์ ๊ฐ์ ์ฐจ์ด๋ฅผ ๋ฐํํ๋ ํจ์๋ฅผ ๋ง๋ค์ด
์ฃผ์ด์ง number์ 1์ฉ ์ฆ๊ฐํ๋ฉฐ number๊ณผ ๋น๊ตํ๋ ๋ฐฉ์์ผ๋ก ์ ๊ทผํ์๋ค.
ํ์ง๋ง ๋ฒ์๊ฐ ( 1 ≤ numbers์ ๊ธธ์ด ≤ 100,000 ), ( 0 ≤ numbers์ ๋ชจ๋ ์ ≤ 10^15 ) ์ผ๋ก ๋งค์ฐ ๋์ด ์ด๋ ๊ฒ ์ ๊ทผํ๋ฉด ํจ์จ์ฑ์์ ํ๋ฝํ๊ฒ ๋๋ค.
๊ทธ๋์ ๋ค๋ฅธ ์์ด๋์ด๋ก ์ ๊ทผํ์๋ค.
1. binary์ ๊ฐ์ฅ ๋ค๊ฐ 0์ธ ๊ฒฝ์ฐ
11000, 11100, ... ์ด๋ฐ ๊ฒฝ์ฐ๋ ๊ทธ๋ฅ +1์ ํ๋ฉด ์ ๋ต์ด ๋๋ค.
if(binary[binary.length - 1] === "0") answer.push(number+1)โ
2. binary์ ๊ฐ์ฅ ๋ค๊ฐ 0์ด ์๋ ๊ฒฝ์ฐ
100111, 111111, 111011 ... ์ด๋ฐ ๊ฒฝ์ฐ๋ ํจํด์ด ์๋ค.
์ฐ์ +1์ ์ ์ฉํ๊ณ ๋นํธ์์ ์ฐจ์ด๊ฐ 2์ด ๋๋๋ก ๋ง๋ค๋ฉด
1. 100111(๊ธฐ์กด ๋น๊ตํ num) -> 101000 -> 101011(๋นํธ์๊ฐ 2๊ฐ ์ฐจ์ด)
2. 0111111(๊ธฐ์กด ๋น๊ตํ num) -> 1000000 -> 1011111(๋นํธ์๊ฐ 2๊ฐ ์ฐจ์ด)
3. 111011(๊ธฐ์กด ๋น๊ตํ num) -> 111100 -> 111101(๋นํธ์๊ฐ 2๊ฐ ์ฐจ์ด)
์ด์ ํจํด์ด ๋ณด์ธ๋ค.
1. ์ ๋ค์์๋ถํฐ ์ฐ์๋ 1์ ์๊ฐ 3๊ฐ์์๋, 2๊ฐ๊ฐ ๋์๊ณ
2. ๋ ๋ค์์๋ถํฐ ์ฐ์๋ 1์ ์๊ฐ 6๊ฐ์์๋, 5๊ฐ๊ฐ ๋์๊ณ
3. ๋ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ค์์๋ถํฐ ์ฐ์๋ 1์ ์๊ฐ 2๊ฐ์์๋, 1๊ฐ๊ฐ ๋์๋ค.
1111 ๊ฐ์ด ๋ค์์๋ถํฐ ์ฐ์๋ ๋นํธ์๋ฅผ 10์ง๋ฒ์ผ๋ก ๋ฐ๊พธ๊ธฐ ์ํด์ ์ฐ์๋ 1์ ๊ฐ์ (n)์ผ๋
2^n - 1 ์ด๋๊ณ , ์์ ๊ณผ์ (1. 2. 3.)์์ ์ค๊ฐ์ +1์ ํ์์ผ๋ฏ๋ก
๊ฒฐ๊ตญ (๊ธฐ์กด ๋น๊ตํ num)์ 2์ง๋ฒ์ผ๋ก ๋ง๋ค์ด ๋ค์์๋ถํฐ ์ฐ์๋ 1์ ์๋ฅผ ์ฐพ์
(์ฐ์๋ 1์ ์ - 1) ^ 2 ์ ๋ํด์ฃผ๋ฉด ๋๋ค.
else{ const oneCnt = findConsecutive1S(binary) answer.push(number + (2 ** (oneCnt-1))) } // ๋ค์์๋ถํฐ ์ฐ์๋ 1์ ๊ฐ์๋ฅผ ์ฐพ์ ๋ฐํ const findConsecutive1S = (str) => { let cnt = 0; let endIdx = str.length - 1; while(str[endIdx] === "1"){ endIdx--; cnt++; } return cnt; }
function solution(numbers) {
var answer = [];
numbers.forEach(number => {
const binary = number.toString(2);
if(binary[binary.length - 1] === "0") answer.push(number+1)
else{
const oneCnt = findConsecutive1S(binary)
answer.push(number + (2 ** (oneCnt-1)))
}
})
return answer;
}
const findConsecutive1S = (str) => {
let cnt = 0;
let endIdx = str.length - 1;
while(str[endIdx] === "1"){
endIdx--;
cnt++;
}
return cnt;
}
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] 3์ฐจ n์ง์ ๊ฒ์ (17687) (0) | 2022.06.24 |
---|---|
[Javascript] n^2 ๋ฐฐ์ด ์๋ฅด๊ธฐ (87390) (0) | 2022.06.23 |
[Javascript] 1์ฐจ ๋ด์ค ํด๋ฌ์คํธ๋ง (17677) (0) | 2022.06.23 |
[Javascript] k์ง์์์ ์์ ๊ฐ์ ๊ตฌํ๊ธฐ (92335) (0) | 2022.06.23 |
[Javascript] ๋ ๋ฐ๋จน๊ธฐ (12913) (0) | 2022.06.23 |