[Codility-JavaScript] BinaryGap (코딜리티 자바스크립트)

안녕하세요 최근에 알게된 코딜리티 사이트에서 가입하고 나면 하는 튜토리얼 알고리즘이 있는 것 같아

기록 차 남깁니다!! 

** 문제의 경우는 사이트에 들어가시면 좀 더 자세히 확인이 가능 합니다!!

// 코딜리티 사이트 

https://app.codility.com

1 Binary Gap

정수인 N에 대하여 바이너리 갭을 구하는 1번째 튜토리얼 입니다. 제로 (0) 의 값이 제일 많은 수를 구하면됩니다.

1과 1사이에 대해서만 

만약에 10000100 이라면  10000100 이 부분이 더 많으니까 리턴 은 4가 되어야 합니다.

하지만 1000000000 으로 된다면 다음 1이 없기 때문에 사이값을 지정할수 없어 리턴은 0이 됩니다.

또 다른 케이스를 볼까요?

11111111 와같이 되어도 0이 개수가 없기 때문에 리턴은 0이 됩니다.

실행 가능한 N의 정수는

• N is an integer within the range [1..2,147,483,647].

와 같습니다. (사실 이부분 때문에 어떻게 풀어야 하나 고민 된 부분이 하나 있습니다. : -> 2진수 변환시 )

예시로 준 값에 대해서는 샘플 결과는

1041 -> 5

32 -> 0 

등등이 있습니다.

** 참고로 해야 할 점 

JavaScript 에서는 Number.prototype.toString을 통해서 2진수로 변환할 수 있습니다.

var numberValue = 1041;

numberValue.toString(2); // "10000010001"

이 방법을 쓰기 위해서 알고리즘을 하는 건 아니니까 최대한 지양 하도록 합시다 !

[풀이]

2진수 변환 을 우선 먼저 해주어야 하는데 일단 단순하게 생각해보았을 경우는

/2 로 나누면서 몫과 나머지를 계산 하는 방식입니다. 

단순 반복문

  while(N>=1){

      // share Check

      let share = N%2;

      binArr.push(share);

      

      // rest Check and Integer

      N = Math.floor(N/2);

      

  }

binArr = binArr.reverse();

우선 N 의 값은 1까지 나누어야 하기 때문에 1보다 낮아질 경우 까지 무한반복을 합니다.

나머지 값(share) 을 찾아서 배열에 추가

JS에서는 /2를 하게되면 실수형 연산이 되기때문에 Math.floor 로 소수점을 버립니다.

위와같이 계산하게되면 2진수는 반대이기 때문에 reverse를 호출하여 이진수 형태를 만듭니다.

(** 문제점이 있다면 아래의 조건이 없었을 경우 아래조건보다 더 커지게 되면

• N is an integer within the range [1..2,147,483,647].

12831273127382173912739012739821739081273980213 // 1.2831273127382173e+46

위와같이 나타나서 2진수 계산이 되지 않습니다. (하지만 조건이 있기에 위와같이 단순계산하는게 속도상 제일 빠릅니다.)

재귀 함수

function s(d,v){

  const share = Math.floor(v / d);

  const rest = v % d;

  

  if(d > share){

    return '' + share + rest;

}else {

    return '' + s(d,share) + rest;

}

}

s(2,1041); // "10000010001"

재귀로 하게되면 위의 N의조건이 없었을시에는 계속 가능합니다. 마지막 콜스택에서

찾아 올라오기 때문에 reverse도 할 필요 없구요 (하지만 속도가 좀더 느리더군요)

갭 구하기 

갭을 구해야 합니다. 조건을 나름 정해 보았습니다.

- 1 다음부터 카운트를 해야 하고 다시 1을 만났을때 그사이에 0 의 값에 대한 카운트는 Fixed가 된다.

(Fixed시 기존에 카운트 값이 있다면 크기 비교 후 더 큰 쪽을 Fixed한다.)

- 1 다음부터 카운트를 하였는데 1이 다시 안나온다면 값을 0으로 Fixed 된다.

- 1 만 나왔을 경우 값은 계속 0을 유지한다. 

- 1이 나오게 되면 진행 중이라는 플래그 값이 필요 할 것 같다.(running)

Binary Gap 은 간단하기에 위와같은 풀이식을 적용한 솔루션 적어 놓겠습니다.

// you can write to stdout for debugging purposes, e.g.

// console.log('this is a debug message');

function solution(N) {

  // write your code in JavaScript (Node.js 8.9.4)

  let binArr = [];

  

  while(N>=1){

      // share Check

      let share = N%2;

      binArr.push(share);

      

      // rest Check and Integer

      N = Math.floor(N/2);

      

  }

  // binary Reverse

  binArr = binArr.reverse();

  // gap Max Value

  let currGapMax = 0 ;

  let running = false;

  

  // 1 1 0 0 0 0 0 0

  binArr.reduce(function(prev,curr,index,arr){

      // check Starting

      if(curr===1 && running ===true){

          currGapMax = currGapMax < prev ? prev : currGapMax;

          prev = 0 ;

          return prev;

      }

      // check Counting

      else if(running === true && curr===0){

          prev+=1;

          return prev;

      }

      else if(curr===1){

          running = true;

          return prev;

      }

  },0);

  

  

  return currGapMax;

  

}

조건이 단순 양수 값이였다면 재귀 형태를 사용 했을 것 같습니다.

(JS의 toString(2) 도 그런 것으로 보입니다.)

N의 조건을 두었기 때문에 위와같이 단순 계산을 사용하였습니다.

감사합니다.