[Codility] 01.Binary Gap (Python)

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

정수 N의 이진수에 대한 Binary Gap(1과 1사이에 있는 0의 개수)의 최대값을 구하는 문제

나의 첫 번째 풀이

나의 첫 번째 풀이는 단순하게 1.정수를 이진수로 변환하고 2. 이진수에서 값을 하나씩 확인하며 Binary Gap을 구하는 방법을 생각했다.

재귀를 활용하여 이진수로 변환하는 효율적인 방법을 생각해보았다. 파라메터로 넘어오는 값인 정수N에 대한 몫이 1이 될 때까지(탈출조건) 재귀를 돌면서 나머지를 뒤에 붙여주는 방식이다.

예를 들어, 10을 이진수로 변경하려면

10은 2x5 + 1 ---> binary = 1
5는 2x2 + 1 ---> binary = 11
2는 2x1 + 0 ---> binary = 011
1 탈출 ---> binary = 1011

def solution(N):
    binary = makeBinary(N)
    return getBinaryGap(binary)

    pass

def makeBinary(num): # 정수를 이진수로 변경하는 함수
    if num == 1:
        return '1'

    devidedNum = int(num / 2)
    rest = num % 2

    return makeBinary(devidedNum) + str(rest)

def getBinaryGap(num): # Binary Gap의 최대값 구하는 함수
    cnt_list = [0]
    cnt = 0
    for i in num[1:]:
        if i == '0':
            cnt += 1
        else:
            cnt_list.append(cnt)
            cnt = 0

    return max(cnt_list)

나의 두 번째 풀이

파이썬의 함수를 잘 활용하면 한줄로 코딩을 할 수 있다.
차례대로

bin(N) # 정수를 이진수로 변환. 0b001 형식으로 출력되어 앞 두 글자는 슬라이싱해줘야함
strip('0') # 끝에 있는 0을 없애줌. ex) 1000100 -> 10001
split('1') # 1을 기준으로 문자열을 잘라 리스트에 넣어줌 ex) '100101'.split('1') = ['00', '0']

리스트의 max값을 구해 그 길이를 리턴해주면 끝.

def solution(N):
    return len(max(str(bin(N)[2:]).strip('0').split('1')))