[알고리즘] Codility Javascript - Binary Gap

HJ·2022년 4월 22일

JavaScript

목록 보기

38/45

문제
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); // 10진수를 2진수로 변환
    const trimmed = binary.substr(0, binary.lastIndexOf('1') +1); // 문자열 0번째부터 끝에서 부터 검색할 값인 '1'까지 자른 뒤 1을 더해준다
    return Math.max(...(trimmed.split('1').map(item => item.length)));
} // 1 기준으로 문자열 자르고 공백 제거한 것의 반복한 길이만큼의 최대값을 구한다

toString: 10진수-> 2진수 변환
substr: 시작 위치부터 해당 길이만큼 문자열 자르기
lastIndexOf(검색할 값 , 시작위치) - 끝에서부터 검색할 값을 찾기 시작
Math.max: 배열에서 최대값 구하기
trim: 공백 제거
split: 구분자 문자열 기준으로 자른 후 배열로 변환