[LeetCode] Binary Gap

1.문제

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

정수 n이 주어질 때 n을 이진수로 바꾼 수에서 1과 1사이의 길이가 가장 긴 경우의 그 길이를 리턴하는 문제이다.

Example 1

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2

Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 3

Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Constraints:

• 1 <= n <= 10^9

2.풀이

1. 문자열을 순회하면서 1이 나올 때 그 다음 숫자부터 끝까지 문자열을 자른다.
2. 자른 문자열에서 1이 처음으로 나올 때 그 사이 길이를 계산한다.
3. max값과 비교하여 큰값이면 max값을 갱신해준다.

/**
 * @param {number} n
 * @return {number}
 */
const binaryGap = function (n) {
  const binary = n.toString(2); // 2진수로 변환
  let max = 0;
  for (let i = 0; i < binary.length; i++) {
    let current = 0;
    if (binary[i] === "1") {
      // 1이라면
      let temp = binary.slice(i + 1); //현재 인덱스 다음부터 뒤쪽배열을 잘라서
      for (let j = 0; j < temp.length; j++) {
        if (temp[j] === "1") {
          // 자른 배열에서 1이나오면 길이를 계산
          current = j + i + 1 - i;
          if (current >= max) {
            // 최댓값과 비교해서 최댓값 갱신
            max = current;
          }
          break;
        }
      }
    }
  }

  return max;
};