[알고리즘/자바스크립트] Codility, Binary Gap 문제 풀이

Codility, Binary Gap

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.

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.

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.

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.

Write an efficient algorithm for the following assumptions:

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

 

 

---

 

 

한동안 프로젝트하느라 바빠서 많이 풀지 못했던 알고리즘 문제들을 다시 풀어보려고 한다.

주로 Codewars에 있는 문제들을 풀다가 며칠전에 주변 사람들에게 Codility 사이트를 추천받아서 일단 가입을 했다.

Codility 사이트의 Lessons 문제들을 오늘부터 하루에 하나씩 차근 차근 풀어보려고 한다.

 

Binary Gap문제는 1부터 2,147,483,647 사이의 숫자들 중에서 하나가 주어지면 

그 숫자를 2진수로 변환했을때 1과 1 사이의 연속적인 0의 길이가 긴 길이를 리턴하는 문제이다.

 

만약에 9라는 숫자가 주어졌다면, 9의 2진수는 1001이므로 가장 긴 0의 길이는 2이다.

529라는 숫자는 1000010001이므로 가장 긴 0의 길이는 4가 된다.

만약에 2진수가 100000이라면 1과 1 사이에 있는 연속적인 0이 없으므로 0을 리턴해야하고

1111과 같이 0이 존재하지 않는다면 역시 0을 리턴하면 된다.

 

 

내가 푼 방법은 다음과 같다.

 

function solution(N) {
  const binaryNum = N.toString(2);
  const binaryGaps = binaryNum.slice(binaryNum.indexOf('1') + 1, binaryNum.lastIndexOf('1'));
  const zeroCounted = binaryGaps.split('1').map(zeros => zeros.length);

  return zeroCounted.length ? Math.max(...zeroCounted) : 0;
}

 

• 먼저 숫자에 toString() 메소드를 사용하여 2진수 string으로 변환한다.
• 1과 1 사이의 0의 길이만 구해야하기때문에 slice() 메소드를 사용해서 처음에 위치하는 1과 끝에 위치하는 1의 인덱스번호로 문자열을 자른다.
• 잘려진 문자열을 '1'을 기준으로 split한다. 그러면 0만 뭉쳐져서 배열로 만들어지는데 이 때 0의 길이를 추출해서 배열을 만들어 zeroCounted 변수에 저장한다.
• zeroCounted 배열의 가장 큰 숫자가 가장 길이가 긴 0의 길이이므로 리턴한다. 만약 배열의 길이가 0이라면 0을 리턴한다.

 

2진수 구하는 방법만 안다면 쉽게 풀 수 있는 문제인 듯 하다.

 

 

 

https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

BinaryGap coding task - Learn to Code - Codility