[codility] BinaryGap

(문제) 주어진 양의 정수 N의 이진표현에서 가장 긴 연속된 0의 간격을 찾는 함수 작성

https://github.com/jaehee-bae/codility/blob/master/codility/tasks/BinaryGap.java

 

(my solution)

1. isGap 변수가 어떤 역할을 하는 변수인 지 직관적으로 와닿지 않음

=> Gap을 카운팅 중이라는 뜻으로 counting으로 수정

2. gapCount 변수의 의미가 모호함 (전체 gap의 개수를 카운팅 했다는 건지, 현재 gap의 개수를 카운팅한 건지)

=> currentGap이 더 직관적임

3. while문 안의 조건문 수정 (1. 중복된 조건 존재  2. 가독성 떨어짐)

4. 시간 복잡도는 O(logN)

package codility.tasks;

public class BinaryGap {
    public static int solution(int N) {
        int gapCount = 0;
        boolean isGap = false;
        int maxGap = 0;

        while (N != 0) {
            int left = N % 2;
            N = N / 2;

            if (isGap && left == 0) {
                gapCount++;
            }

            if (isGap && left == 1 && gapCount > maxGap) {
                maxGap = gapCount;
            }

            if (left == 1) {
                isGap = true;
                gapCount = 0;
            }
        }

        return maxGap;
    }
}

 

 

(chatGPT solution)

1. 비트연산자 >> 사용하여 오른쪽으로 하나 이동. 이는 2로 나누는 것과 동일한 효과로 while문 반복할 때마다 N은 2로 나눈 몫이 됨

2. 비트연산자 & 사용하여 마지막 비트가 0인지 1인지 확인함

2. 시간복잡도는 O(logN)

class Solution {
    public int solution(int N) {
        int maxGap = 0;
        int currentGap = 0;
        boolean counting = false;

        while (N > 0) {
            if ((N & 1) == 1) {
                if (counting) {
                    maxGap = Math.max(maxGap, currentGap);
                }
                currentGap = 0;
                counting = true;
            } else {
                if (counting) {
                    currentGap++;
                }
            }
            N >>= 1;
        }

        return maxGap;
    }
}