파이썬으로 숫자의 이진 표현에서 1 사이의 최대 거리 찾기

어떤 수 N이 주어졌을 때, N의 이진수 표현에서 인접한 두 개의 1 사이의 최대 거리를 구하는 프로그램을 파이썬으로 작성해 보겠습니다. 만약 1이 두 개 미만으로 존재한다면 0을 반환합니다.

문제 이해하기

예를 들어 입력이 71이라면 출력은 4가 됩니다. 71을 이진수로 변환하면 1000111이 되는데, 여기에는 네 개의 1이 있습니다. 첫 번째 1과 두 번째 1 사이의 거리는 4이고, 나머지 1들은 서로 거리가 1입니다. 따라서 가장 긴 거리는 4입니다.

해결 접근 방법

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

• N의 이진 표현 비트들을 리스트 K로 만듭니다.
• Max := 0, C := 0, S := 0으로 초기화합니다.
• Flag := False로 초기화합니다.
• i를 0부터 K의 크기까지 반복합니다.
  • K[i]가 '1'이고 C가 0이며 Flag가 False라면, C := i로 설정하고 Flag := True로 변경합니다.
  • 그렇지 않고 K[i]가 '1'이며 Flag가 True라면, S := i로 설정하고 Max < |S − C|일 때 Max := |S − C|로 갱신한 후 C := S로 업데이트합니다.
• 반복이 끝나면 Max를 반환합니다.

파이썬 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

def solve(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

n = 71
print(solve(n))

입력

71

출력

4

시간 복잡도

이 알고리즘은 N의 이진 표현 길이에 비례하여 O(log N)의 시간 복잡도로 동작하며, 비트를 저장하는 데 필요한 추가 공간 역시 O(log N)입니다. 입력 크기와 무관하게 매우 효율적으로 동작하므로 큰 수에 대해서도 빠르게 결과를 얻을 수 있습니다.