BinaryGap

/Codility

문제 해석

요약

주어진 정수 N을 2진법으로 나타냈을때, 앞뒤가 1로 막힌 연속된 0 중에서 가장 긴 0의 개수를 리턴해야 한다.
10001001의 경우 3을 리턴 하는 식이다. 만약 1000이라면, 막혀있지 않으므로 0을 리턴.
N의 범위는 1부터 2,147,483,647이다.

전문

🇰🇷 번역

양의 정수 N내의 Binary Gap은 N을 이진법으로 표현했을때 양쪽 끝이 1로 둘러싸인 연속된 0의 최대 시퀀스이다.

숫자 9는 이진법으로 1001로 표현되고 binary gap의 길이는 2이다. 숫자 529는 이진법으롤 1000010001이며, 2개의 binary gap이 있다. 하나의 길이는 4이고, 나머지는 3이다. 숫자 20은 10100으로 표현되며 길이가 1인 binary gap을 포함한다. 숫자 15는 111로 표현되고, binary gap이 없다. 32는 100000로 표현되는데 마찬가지로 binary gap이 없다.

함수를 작성하시오:

function solution(N);

양의 정수 N이 주어지고, 가장 긴 binary gap의 길이를 리턴한다. 만약 binary gap을 가지고 있지 않다면, 0을 리턴한다.

N = 1041로 주어지면, 5를 리턴해야한다. N을 2진법으로 나타내면 10000010001이고 가장 긴 binary gap은 길이가 5이기 때문이다. N = 32라면, 함수는 0을 리턴한다. 2진법으로 표현하면 100000이기 때문에, binary gap이 없기 때문이다.

다음과 같은 가정을 따라 효율적인 알고리즘을 작성하시오:

  • N은 [1..2,147,483,647] 범위 내의 정수이다.

🇺🇸 원문

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].

🤔 문제 해결 방법 구상

우선 주어진 N을 2진법으로 바꿔야 한다. 이때 toSting()을 사용하면 편리하다.

변환된 2진법을 이제 살펴봐야하는데.... for문을 돌면서 Two Pointers를 이용하면 어떨까 싶다. 하나의 포인터는 앞으로 나아가면서 비교, 다른 하나의 포인터 길이를 기록하는 변수!

  1. toSting(2)을 통해 N을 2진법으로 변환
  2. 최댓값을 저장하는 변수 maxGap 설정
  3. for문을 돌며, 0이 나오면 gap 증가

    • 참고로 무조건 1로 시작할테니 인덱스 0은 제외하고 1부터 시작
  4. 다음 1을 만나면 최댓값과 비교

    • 다음 gap을 카운트해야하므로, gap은 0으로 재할당
  5. 최댓값 리턴

코드 구현

function solution(N) {
  const binary = N.toString(2);
  let maxGap = 0;
  let gap = 0;

  for (let i = 1; i < binary.length; i++) {
    if (binary[i] === '0') {
      gap++;
    } else {
      maxGap = maxGap < gap ? gap : maxGap;
      gap = 0;
    }
  }

  return maxGap;
};

결과 분석

Task Score: 100%
Correctness: 100%
Performance: 100%

테스트 모두 통과!
N의 크기에 따라 시간이 증가하므로, 시간복잡도는 O(n), 추가 메모리 없으므로 공간복잡도는 O(1)이다.

기존에 풀었던 문제(Two Sum)에서 indexOf가 시간복잡도를 해치는 것 같아서 우선적으로 배제하였다. 2진수로 변환시키는 메소드를 알고 있어서 생각보다 간단하게 풀 수 있었다. 만약 메소드를 쓰지 않으려면, 주어진 N을 2로 계속 나누면서 나머지를 모아야한다.

마무리

메소드를 쓰면 확실히 코드의 길이는 짧아진다. 그러나 코드의 길이가 복잡도를 증명해주는 것은 아니다. 무엇이 더 효율적인지 생각하면서 문제를 풀어야한다.
알고리즘 문제를 풀다보니 bit에 대한 공부가 필요함을 느낀다. bit와 연관된 문제가 은근 많이 나오는데, 매번 풀때마다 삐그덕거리는 기분이다. 또한, 꼭 bit로 풀지 않아도 되는 문제지만, 알고있으면 문제를 더욱 간단하게 풀 수 있는 경우도 있더라. 좀 더 자세히 공부를 해봐야 겠다.
참고로 미리 제한을 둔 범위의 숫자 2,147,483,647는 32비트 정수형의 최댓값이다. 이와 관련되어 흥미로운 이야기가 위키피디아에 있어서 재밌게 읽었다.

Reference & Learn More

MDN toString()
Wikipedia 2,147,483,647

Tags
Comments