[코딜리티] BinaryGap(이진 갭 알고리즘)

문제

• 양수의 int 형 숫자를 이진수로 표현하였을때 1과 다른 1의 차이(Binary Gap), 즉 1과 다른 1사이의 0의 개수가 최대인 경우를 찾아야 한다.

• 예를들면 9는 이진수로 1001 이니 1과 1사이에 0이 2개가 있어 Binary Gap의 길이는 2이다. 529같은 경우는 이진수1000010001 이며 Binary Gap 은 총 2개인데, 100001의 부분의 4와 1001 부분의 3이다. 이때 최대값은 4이므로 4를 리턴하면 된다.

• 정수의 범위는 1~2,147,483,647 이다.(int형의 양수 최대 표현 범위)

• 복잡도 요구사항(시간복잡도 O(log(N)), 공간복잡도 O(1))

코드

function readMaxValueInResult (result){

        const result_split = result.split('1');

    let max = 0

    if (result_split.length >= 3){

    result_split.forEach((value,index) => {

        if (index == 0){

        max = value.length;

        }

        

        if (max < value.length){

            max = value.length;   

        }

    })

    }

    return max

}

function solution(N) {

    let result = "";

    let m = 0;

    let mod = 0;

    let b = false;

    

    while(!b){

        m = parseInt(N / 2, 10);

        mod = parseInt(N % 2, 10);

        if (mod == 1){

            result += "1";

        } else {

            result += "0";

        }

        

        N = m;

        

        if (m <= 1){

            b = true;

            result += '1';

            result = result.split("").reverse().join("");

            result = readMaxValueInResult(result);

        }

    }

    return result

} 

처음으로 풀어본 알고리즘 문제다.

다 풀고 나서 다른 사람의 코드를 보니, 훨씬 간단했다.

푸는 방법은 다양하지만, 더 쉽고 더 간단하고 빠르게 풀 수 있는 방법을 지속적으로 공부해나가야겠다.