Codility Lesson1. Iterations - BinaryGap

세나정·2023년 4월 24일

[Codility (코딜리티) 코딩테스트]

목록 보기

1/19

Tasks

양의 정수 N 내의 이진 간격은 N 의 이진 표현에서 양쪽 끝이 1로 둘러싸인 연속 0의 최대 시퀀스입니다.

예를 들어, 숫자 9는 이진 표현 1001 을 가지며 길이 2의 이진 간격을 포함합니다. 숫자 529는 이진 표현 1000010001 을 가지며 길이 4 중 하나와 길이 3의 두 이진 간격을 포함합니다. 숫자 20은 이진 표현 10100을 가지며 다음을 포함합니다 . 길이가 1인 하나의 이진 갭. 숫자 15는 이진 표현 (1111) 을 갖고 이진 갭이 없습니다. 숫자 32는 이진수 표현이 100000 이고 이진수 간격이 없습니다.

함수 작성:

함수 솔루션(N);

양의 정수 N이 주어지면 가장 긴 이진 간격의 길이를 반환합니다. N에 이진 간격이 포함되어 있지 않으면 함수는 0을 반환해야 합니다.

예를 들어, N = 1041이 주어지면 함수는 5를 반환해야 합니다. N은 이진수 표현이 10000010001 이므로 가장 긴 이진 간격의 길이는 5이기 때문입니다. N = 32가 주어지면 함수는 0을 반환해야 합니다. 바이너리 갭이 없습니다.

다음 가정에 대한 효율적인 알고리즘을 작성하십시오 .

N은 [ 1 .. 2,147,483,647 ] 범위 내의 정수입니다 .
https://codility.com/media/train/Iterations.pdf

내 풀이

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message ');

function solution(N) {
    // Implement your solution here
    N = 0+N.toString(2)+0
    
    ans = [];

    RES = N.split('1').filter( e => e.length >= 1)

    RES.pop()
    RES.shift()

    for (let v of RES) {
        ans.push(v.length)
    }

    return ans.length !== 0  ? Math.max(...ans) : 0
}

문제부터 설명하자면 이진수로 나타냈을 때 1사이에 들어있는 0의 갯수가 가장 큰 것을 구하면 되는 문제이다.
529 -> 1000010001
20 -> 10100
32 -> 100000

하지만 여기서 32처럼 1로 묶여져 있지 않으면 0을 리턴 해야했다.

그렇기때문에 처음 이진수로 바꾸어줄 때 0을 앞 뒤로 넣고
split을 통해 1로 나눈다면
32의 경우 [ "0", "000000" ] 가 나오고 거기에서 pop과 shift로 앞뒤를 빼준다면
그의 길이는 0이 되기 때문에 1로 묶여져 있지 않은 애를 뺴줄 수 있음

결론적으로 그렇게 나온 배열에서 삼항연산자를 통해 return을 해주면 된다.

다른 사람 풀이

function solution(N) {

    const binnary = N.toString(2);
    let max = 0;
    let counter = 0;
    let startCount = false;
    
    for (const char of binnary) {
        if (char === '1' && startCount === false) {
            startCount = true;
        } 
        
        if (char === '0' && startCount) {
            counter++;
        }
        
        if (char === '1' && startCount === true ) {
            max = Math.max(max, counter);
            counter = 0;
        }
    }
    
    return max;
}

웬 외국인 형님이 푸신 코드인데 ..
보면 startCount를 스위치처럼 활용해서 풀었다
배열의 순회를 시작하자마자 1로 시작하고 스위치가 꺼져있다면
스위치를 켠 후에 0의 갯수에 따라서 couter를 늘리는 것이다.