Codility의 BinaryGap 문제 풀이 및 해답 (C++ )

안녕하세요. Twodragon입니다.

1일 1 코딩을 하려고 했으나 생각보다 쉽지가 않습니다. 띄엄띄엄하더라도 최대한 습관이 되도록 노력해보겠습니다. 1일 1 커밋도 생각보다 어렵고, 역시 사소한 습관 하나를 만드는 것이 가장 어려운 일인 것 같습니다. 모두들 하나씩 사소한 습관으로 멋진 사람이 되길 바랍니다.

 

 

- 코딜리티 바이너리 갭 문제:

 

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:

int solution(int 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].

  Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

- 코딜리티 바이너리 갭 문제 풀이 과정:

 

정수 N을 2진수로 표현했을 때, 1과 1 사이의 0의 공백(Gap)을 카운트하는 문제로, 0의 개수를 구하는 문제입니다. 단, 1과 1 사이의 0의 개수 중 가장 긴 값을 반환해야 합니다. 먼저 binaryNum [32]를 설정하여 binary를 2진수로 변환하여 배열로 만듭니다. getBinGap는 Check 된 gap의 값을 가져오고, 최댓값을 보유하도록 함수를 구현하였습니다. checkBinGap에서는 binary gap을 1과 0 사이의 값의 길이를 count 합니다. 따라서 총 바이너리 배열과 바이너리 갭의 최댓값인 2개의 함수를 구현하였습니다. 처음으로 코딜리티 문제를 풀어보면서 해커랭크랑은 다른 재미가 있습니다. 

 

 

- 코딜리티 바이너리 갭 해답:

#include <cmath>
using namespace std;

int checkBinGap(int ban[], int size, int pos){
    int count = 0;

    if(ban[pos] == 1){
        for(int i = pos+1; i < size; i++){
            if(ban[i] == 0){
                ++count;
            }
            else{
                return count;
            }
        }
    }
    return 0;
}


int getBinGap(int ban[], int size){
    int maxVal = 0;

    for(int i=0; i < size; i++){
        maxVal = max(maxVal, checkBinGap(ban, size, i));
    }
    return maxVal;
}

int solution(int N) {
    // write your code in C++14 (g++ 6.2.0)
    // array to store binary number 
    int binaryNum[32]; 
  
    int i = 0; 
    while (N > 0) { 
        binaryNum[i] = N % 2; 
        N /= 2; 
        i++; 
    }
    
    
    return getBinGap(binaryNum, i++);
}