Codility Lession1 문제

문자열 처리, 시퀀스 탐색, 그리디, 비트조작

양의 정수N안의 **이진 갭(Binary Gap)**이란,N을 2진수로 표현했을 때,**양쪽이 1로 둘러싸인 연속된 0의 시퀀스(연속된 0들)**중 가장 긴 것 을 말합니다.

예를 들어, 숫자 9는 이진수로 표현하면 1001이고, 길이가 2인 이진 갭이 포함되어 있습니다.

숫자 529는 이진수로 1000010001이고 이안에는 두 개의 이진갭이 있습니다.하나는 길이 4(0000), 하나는 길이 3(000).

숫자 20은 이진수로 10100 을 가지며 길이가 1인 이진갭 하나를 포함합니다.

숫자 15는 이진 표현 1111 을 가지며 이진 갭이 없습니다.

숫자 32는 이진 표현 100000 을 가지며 이진 간격이 없습니다.

N은 [1.. 2,147,483,647]라고 가정할 때, 효율적인 알고리즘을 작성합니다.

function solution(N) {
  const binaryStr = N.toString(2); // 10진수를 2진수 문자열로 변경
  let maxGap = 0;
  let currentGap = 0;
  let counting = false;

  for (let i = 0; i < binaryStr.length; i++) {
    const bit = binaryStr[i];

    if (bit === "1") {
      if (counting) {
        // 갭 종료 → 최대값 갱신
        maxGap = Math.max(maxGap, currentGap);
      }
      // 첫 1이든, 이후든 counting은 항상 시작 또는 유지
      currentGap = 0;
      counting = true;
    } else if (counting) {
      // 0을 만나고, counting 중이면 갭 길이 증가
      currentGap++;
    }
  }

  return maxGap;
}