[분석] Codility - BinaryGap - Javascript

Codility 연습문제 > BinaryGap > Javascript
실제 문제의 저작권은 Codility 에 있으므로 전체 문제의 내용은 Codility 페이지를 방문해 확인하세요.

[문제 및 조건]

양의 정수 N이 주어지면 가장 긴 2진 간격의 길이를 반환하라. N에 2진 갭이 없으면 함수는 0을 반환해야 한다. N은 [1…2, 145,483,647] 범위 내의 정수이다.

1. 0과 1로 되어있는 2진 수가 주어진다.
2. 2진 갭의 조건은 양쪽에 1로 둘러싸인 연속적인 0의 시퀀스를 의미한다.
3. 예를 들어 숫자 529를 2진으로 표현하면 1000010001 로 표시할 수 있고, 이 2진수는 100001, 10001 두 개의 갭을 가지며 가장 긴 길이는 0이 4개인 4이다.
4. 1111 또는 1000000 과 같은 2진수는 2진 간격이 없으므로 길이는 0이 된다.
   
   

[분석]

1. 숫자가 주어지면 숫자를 2진수로 표현해야한다.
2. 양쪽에 1로 둘러사인 연속적인 0의 형태를 가진 그룹을 찾는다.
3. 찾은 그룹중에서 0의 길이가 가장 긴 값을 반환한다.
4. 만약 갭이 없으면 0을 반환한다.

숫자는 1부터 시작이고, 이 문제의 경우 시간 복잡도에 대한 효율성을 따지지 않는 문제이다.

[풀이]

1. 2진수를 만드는 방법은 대상 숫자를 2로 나눈 나머지의 역순 정렬이다.
2. 문자형태의 반복문은 index 값 조회가 필요없는 for of 를 이용해 값만 분석한다.
3. 문자형 숫자의 숫자형태 값이 1인지 아닌지에 따라 특정 갭 조건의 count 를 설정한다.
4. 시간 복잡도 보다 풀이의 과정을 설명하기 위해 쉽게 풀어써보자.

function solution(N) {
  let number = N;
  let binaryStr = '';
  let group = [];
  let count = 0;
  
  //2진수를 만든다
  while (true) {
    if (!number) break; // while(xxx) 안에 들어가도 상관없다.

    binaryStr = String(number % 2) + binaryStr; // 덧샘은 원래 String 값으로 조합되지만 일단 String으로 변환해 타입 정리.
    number = Math.floor(number / 2); // 새로운 몫을 구한다.
  }
	
  //2진수를 그룹으로 정의한다.
  for (const item of binaryStr) {
    if (Number(item) === 1) {
      (count > 0) && group.push(count); // 1로 끝나는 경우, 이전에 0 count가 존재하면 그룹으로 판단해 push한다.
      count = 0; // 초기화
    } else {
      count++; // 1로 둘러싸인 0에 대한 개수만 증가시킨다.
    }
  }
	
  //2진 갭의 0길이중 가잔 긴 값 또는 0을 반환한다.
  return group.length ? Math.max(...group): 0;
}

[마치며]

BinaryGap 연습문제는 쉬운편입니다. 물론 성능에 대한 평가가 없기 때문에 위의 코드만으로도 답을 구할 수 있습니다. 그래도 시간이 된다면 for 구문은 리펙토링을 통해 최적화 해야할 것 같습니다.