[Codility] BinaryGap

https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

 

 

문제 설명

Binary gap은 어떤 양의 정수 N을 2진수로 표현했을 때, 양쪽이 1로 둘러싸인 연속된 0들의 구간 중 “최대 길이”를 의미한다.

 

예시 

1. N = 9
   • 2진수: 1001
   • 1001 → 길이 2인 binary gap 하나
2. N = 529
   • 2진수: 1000010001
   • 1000010001 → 길이 4, 길이 3인 gap 두 개 → 최대값 4
3. N = 20
   • 2진수: 10100
   • 10100 → 가운데 0은 길이 1짜리 gap, 마지막 00은 오른쪽에 1이 없어서 gap 아님
4. N = 15
   • 2진수: 1111
   • 0이 없으므로 gap 없음 (0)
5. N = 32
   • 2진수: 100000
   • 100000 → 1로 닫히지 않은 0들만 있으므로 gap 없음 (0)

 

접근 방식

1. 정수를 2진수 문자열로 변환하기

String binary = Integer.toBinaryString(N);

 

2. 진수 문자열을 왼쪽부터 오른쪽으로 순회하면서 “1로 둘러싸인 0 구간”의 최대 길이를 찾기

1. 첫 번째 1을 만나기 전까지는 gap을 세지 않는다.
2. 1을 만나면
   • 이미 한 번 1을 만난 상태였다면 (즉, started == true), 지금까지 센 0(count)을 최대값(max)과 비교해 갱신
   • gap을 셀 수 있는 상태로 전환 (started = true)
   • 새로운 gap을 위해 count = 0 초기화
3. 0을 만나면
   • 첫 1을 이미 만난 상태(started == true)일 때만 count++
   • 아직 1을 본 적 없다면 (started == false) → gap이 아니므로 무시
4. 문자열 순회를 모두 마친 후 max를 반환
   • 마지막이 1로 끝나지 않는 경우는 자연스럽게 gap으로 계산하지 않음

 

 

나의 풀이 코드

class Solution {
    public int solution(int N) {
        String binary = Integer.toBinaryString(N);

        int max = 0; // 가장 긴 binary gap 길이
        int count = 0; // 현재 0의 개수
        boolean started = false; // 첫 번째 1을 만났는지 여부

        for (int i = 0; i < binary.length(); i++) {
            char c = binary.charAt(i);

            if (c == '1') {
                // 이미 1을 만난 이후라면, 지금까지 센 0의 길이를 max와 비교
                if (started) {
                    max = Math.max(max, count);
                }
                
                // 이제부터 gap을 셀 수 있는 상태
                started = true;
                count = 0; // 새로운 gap을 위해 0 카운트 초기화
            } else {
                // 1을 한 번이라도 만난 이후에만 gap으로 카운트
                if (started) {
                    count++;
                }
            }
        }

        return max;
    }
}

 

 

비트 연산 풀이 (로깅 버전)

class Solution {
	public int solution(int N) {
        System.out.println("===== Binary Gap Log Start =====");
        System.out.println("초기 N = " + N + " (" + Integer.toBinaryString(N) + ")");

        int max = 0;
        int count = 0;

        // (1) 끝의 0 제거
        System.out.println("\n--- Step 1: 끝의 0 제거 과정 ---");
        while (N > 0 && (N & 1) == 0) {
            System.out.printf("LSB = 0 → 제거 대상, N >>= 1 실행\n");
            N >>= 1;
            System.out.println("현재 N = " + N + " (" + Integer.toBinaryString(N) + ")");
        }
        System.out.println("끝의 0 제거 완료 → N = " + N + " (" + Integer.toBinaryString(N) + ")");

        // (2) 본격 gap 계산
        System.out.println("\n--- Step 2: Gap 계산 시작 ---");
        while (N > 0) {
            int lastBit = N & 1;
            System.out.println("\n현재 N = " + N + " (" + Integer.toBinaryString(N) + "), LSB = " + lastBit);

            if (lastBit == 0) {
                count++;
                System.out.println("0 발견 → count 증가: " + count);
            } else {
                System.out.println("1 발견 → gap 종료: count = " + count);
                max = Math.max(max, count);
                System.out.println("max 업데이트 = " + max);
                count = 0;
            }

            System.out.println("N >>= 1 실행 (다음 비트로 이동)");
            N >>= 1;
        }

        System.out.println("\n===== Binary Gap 계산 완료 =====");
        System.out.println("최종 결과 max = " + max);

        return max;
    }
}