Binary Gap 문제

---

문제

숫자를 이진수로 변환하여 1과 1사이의 길이 수를 출력

---

아이디어

1. 숫자를 바이너리 문자로 변환 후 순회하면서 0 카운트 갱신

• 구현이 가장 직관적
• 디버깅, 테스트 쉬움
• 문자열 변환·할당 비용이 있음
• O(logN)

2. 비트 연산 단일 루프 방식

• 순회 N > 0
• N & 1 으로 LSB 조사
• N >>= 1 로 한 비트씩 오른쪽으로 이동
• 문자열 변환 없이 비트만 직접 다름, O(1), 속도 측면에서 매우 효율적
• 비트 마스크·시프트에 익숙해야함

3. 정규 표현식 활용

• 2진 문자열에서 1 ( 0+ ) 1 패턴을 모두 찾아서 그룹 길이의 최댓값
• 코드가 한두 줄로 간결
• 정규식 매칭 비용이 있고, 가독성이 다소 떨어질 수 있음

4. 수학적 모듈로 연산

• N % 2 로 LSB를 구하고
• N /= 2 로 우측 쉬프트와 동일한 효과를 내면서
• 0,1 카운팅 로직을 적용
• 비트 연산과 유사하지만 더 익숙한 산술 연산 사용 가능
• 나눗셈 연산이 비트 연산보다 약간 느림

정리

표 정리

방법시간 복잡도공간 복잡도구현 난이도

방법	시간 복잡도	공간 복잡도	구현 난이도
문자열 변환	O(log N)	O(log N)	★☆☆
비트 연산 단일 루프	O(log N)	O(1)	★★☆
정규 표현식	O(log N·M)	O(log N)	★★☆
모듈로 연산	O(log N)	O(1)	★★☆

 

어떤 방식으로 사용하면 좋을까?

효율적이면서 실용적인관점이라면

• 비트 연산이 주 기능으로 작용하고 사람 친화적 소스인지 순수 비트 계산 자체로 할 것인지
• 오직 효율성이라면 비트 연산
• 실용적?을 생각한다면 모듈로

---

 

풀이

class Solution {
    public int solution(int N) {
        int maxGap = 0;
        int curGap = 0;

        // 맨 끝(LSB 방향)에 있는 0들은 gap이 될 수 없으므로, 첫 번째 1이 나올 때까지 제거
        while (N > 0 && (N & 1) == 0) {
            N >>= 1;
        }

        // 실제 gap 카운팅
        while (N > 0) {
            if ((N & 1) == 0) {
                // 0 비트가 나오면 현재 gap 길이 증가
                curGap++;
            } else {
                // 1 비트가 나오면 지금까지 센 gap과 비교하여 최댓값 갱신 후 초기화
                maxGap = Math.max(maxGap, curGap);
                curGap = 0;
            }
            // 다음 비트로 이동
            N >>= 1;
        }

        return maxGap;
    }
}

1. 반환할 최대 갭, 현재 갭 변수 선언
2. 1 ( 0+ ) 1가 되지 않는 0을 제거
3. 순회를 통해 0이면 카운트 1이면 최대 갭 갱신, 현재 갭 초기화
4. 정수 쉬프트
5. 모든 순회 끝나면 최대 갭 반환

---

참조

제공 사이트: https://app.codility.com/programmers/lessons/1-iterations/