Codility #1 - BinaryGap

문제: https://codility.com/programmers/task/binary_gap/

Codility 의 첫 번째 문제를 풀어봤습니다. 32비트의 integer가 주어졌을 때 해당 integer 를 binary 로 표현할 때 연속적으로 보이는 0의 개수를 binary gap 이라 할 때 가장 긴 binary gap 를 반환하는 문제입니다.

쉬운 문제라 생각하며 별 생각없이 아래와 같이 풀었더니 답은 맞았지만 33% 의 점수를 얻었습니다.

my solving

c++

#include <algorithm>
using namespace std;
 
int solution1(int num)
{
    int count = 0;
    int ret = 0;
    while (num > 0)
    {
        if (num % 2 == 0)
            count++;
        else
        {
            ret = max(ret, count);
            count = 0;
        }
        num /= 2;
    }
    return ret;
}
 

제가 너무 naive 하게 풀었던 모양입니다. 이번에는 시간 복잡도를 고려하여 bit mask 를 사용하는 방법으로 풀어봤습니다.

my solving

c++

#include <algorithm>
using namespace std;
 
int solution2(int N)
{
    int ret = 0;
    int lastIndex = -1;
    
    //N is 32 bit integer
    for (int i = 0; i < 32; i++)
    {
        int bit = 1 << i;
 
        if (bit > N)
            return ret;
 
        if ((N & bit) > 0)
        {
            if (lastIndex == -1)
                lastIndex = i;
            else
            {
                int count = (i - lastIndex) - 1;
                ret = max(ret, count);
                lastIndex = i;
            }
        }
    }
    return ret;
}

score: 100%

Codility 는 다른 사이트에 비해 더 나은 답을 찾을 수 있도록 유도해주는 점이 좋지만 무료로 이용할 경우 일부 문제만 풀 수 있다는 점이 아쉬운거 같습니다.