๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[Javascript] 2๊ฐœ ์ดํ•˜๋กœ ๋‹ค๋ฅธ ๋น„ํŠธ (77885)

๋ฌธ์ œ๋งํฌ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - 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;
}