파이썬 바이너리 갭(Binary Gap): 이진수에서 연속된 1 사이의 최대 거리 구하기

바이너리 갭(Binary Gap) 문제란?

양의 정수 N이 주어졌을 때, N을 이진수로 표현했을 때 나타나는 두 개의 연속된 1 사이의 최대 거리를 구하는 것이 이번 문제의 핵심입니다. 만약 이진 표현에 1이 하나뿐이거나 연속된 1의 쌍이 존재하지 않는다면 0을 반환하면 됩니다.

예시로 이해하기

입력값이 22라고 가정해 보겠습니다. 22를 이진수로 변환하면 10110이 됩니다.

• 22의 이진 표현에는 1이 세 개 있습니다.
• 연속된 1의 쌍은 두 개입니다.
• 첫 번째 쌍의 거리는 2이고, 두 번째 쌍의 거리는 1입니다.
• 따라서 정답은 두 거리 중 더 큰 값인 2가 됩니다.

해결 접근 방법

다음 단계를 따라 문제를 해결할 수 있습니다.

• N의 이진 표현을 비트 리스트 K로 변환합니다.
• Max := 0, C := 0, S := 0으로 초기화하고, Flag := False로 설정합니다.
• i를 0부터 K의 길이까지 반복하며 다음을 수행합니다.
  • K[i]가 '1'이고 C가 0이며 Flag가 False라면, 첫 번째 1의 위치를 기록합니다(C := i, Flag := True).
  • K[i]가 '1'이고 Flag가 True라면, 현재 위치를 S := i로 저장합니다. 이후 Max < |S − C|라면 Max := |S − C|로 갱신하고, C := S로 업데이트합니다.
• 반복이 종료되면 Max를 반환합니다.

파이썬 구현 예제

아래 코드를 통해 실제 동작을 확인해 보세요.

class Solution:
    def binaryGap(self, N):
        B = bin(N).replace('0b', '')
        K = list(str(B))
        Max = 0
        C = 0
        S = 0
        Flag = False
        for i in range(len(K)):
            if K[i] == '1' and C == 0 and not Flag:
                C = i
                Flag = True
            elif K[i] == '1' and Flag:
                S = i
                if Max < abs(S - C):
                    Max = abs(S - C)
                    C = S
        return Max

ob = Solution()
print(ob.binaryGap(22))

실행 결과

입력:

22

출력:

2

마무리

이 알고리즘은 이진 문자열을 한 번만 순회하므로 시간 복잡도는 O(log N)입니다(N의 비트 길이에 비례). bin() 함수로 손쉽게 이진수를 얻고, 플래그 변수를 활용해 첫 번째 1과 이후 등장하는 1의 위치 차이를 추적하는 것이 핵심 아이디어입니다. LeetCode의 'Binary Gap' 문제 등 코딩 테스트에서 자주 등장하는 유형이므로, 위 접근 방식을 익혀 두면 다양한 비트 조작 문제에 응용할 수 있습니다.