Codility - BinaryGap / JavaScript 문제 해석 및 풀이

BinaryGap

Find longest sequence of zeros in binary representation of an integer.
정수를 2진수로 변환했을 때 가장 긴 0의 연속 길이 찾기

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.
양의 정수 N에 있어서 바이너리 갭이란, 2진수로 변환한 N에서 양 끝이 1로 둘러쌓인 0의 연속을 말한다.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.
예를 들면, 9는 2진수로 변환하면 1001이고 길이 2의 바이너리 갭 하나를 갖는다. 529는 2진수로 변환하면 100010001이며 길이 4와 길이 3의 2개의 바이너리 갭을 갖는다. 20은 2진수로 변환하면 10100이며 길이가 1인 하나의 바이너리 갭을 갖는다. 15는 2진수로 변환하면 1111이며 바이너리 갭을 갖지 않는다. 32는 2진수로 변환하면 100000이며 이 또한 바이너리 갭을 갖지 않는다.

Write a function:

function solution(N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.
양의 정수 N의 가장 긴 바이너리 갭을 반환하는 함수를 작성하시오. 바이너리 갭이 없다면 0을 반환하면 된다.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.
예를 들어, N = 1041이라면 함수는 5를 반환한다. 왜냐하면 N을 2진수로 변환하면 10000010001이므로 가장 긴 바이너리 갭은 5이다. N = 32 이 주어진다면 함수는 0을 반환해야한다. 이 경우 N은 2진수로 변환 시 100000이므로 바이너리 갭을 갖지 않기 때문이다.

Write an efficient algorithm for the following assumptions:
아래 가정을 위한 효율적인 알고리즘을 작성하시오:

N is an integer within the range [1..2,147,483,647].
정수 N은 1부터 2,147,483,647까지의 범위를 가진다.

• 문제 링크

나의 풀이

function solution(N) {
	const binary = N.toString(2);
    const gapSet = new Set();

    let gapLength = 0;

    for (let i = 0; i < binary.length; i++) {
      const now = binary[i];
      const prev = binary[i - 1];
      if (now === '1' && prev === '0' && gapLength) {
        gapSet.add(gapLength);
        gapLength = 0;
      } else if (now === '1' && prev === '0' && !gapLength) {
        gapSet.add(gapLength);
        gapLength = 0;
      } else if (now === '0'){
        gapLength++;
      }
    }
	return gapSet.size ? Math.max(...gapSet) : 0;
}

내가 처음 푼 풀이는 위와 같다.

풀고나서 검색해보니 재귀함수로 푸는 방식도 있고, split으로 푸는 방식도 있었다.

위의 split으로 푼 방식에서는 정규 표현식으로 오른쪽, 왼쪽을 다듬었는데, 2진수로 변환하면 0으로 시작할 일은 없을 것 같아서(확실한가?! 나중에 toString(2)와 2진법에 대해 깊이 탐구해봐야겠다) lastIndexOf와 substr으로 대체해 아래와 같이 다시 풀어봤다. 한줄로도 표현할 수 있겠지만 그래도 3줄로 나누는 게 이해하기 쉬워 보인다.

function solution(N) {
	const binary = N.toString(2);
	const trimmed = binary.substr(0, binary.lastIndexOf('1') + 1);
	return Math.max(...(trimmed.split('1').map(item => item.length)));
}