binary gap

BinaryGap coding task - Learn to Code - Codility

Q.

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

def solution(N)

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

 

🤔생각해보기

최근 신청한 코딩테스트가 codility에서 할 수도 있다고 해서 연습하러 와봤습니다.

문제가 영어로 되어있어서 약간 당황했으나 천천히 문제를 해석해보면 주어진 숫자의 이진수에서 연속된 0의 개수가 가장 큰 값을 묻고 있습니다. (파파고나 구글번역기의 도움을 얻으셔도 됩니다.)

529의 경우 이진수로 바꾸면 1000010001 이 되는데 여기서는 0000 이 가장 길게 연속되고 있으므로 4를 얻어내면 되겠습니다.

해당 이진수로 루프를 돌다가 0이 나오면 스택에 쌓아두고 이외의 숫자가 나오면 스택에 쌓인 0의 개수를 저장해둔 후 스택을 초기화시키면 됩니다.

성공 코드

def solution(N):
    s = str(bin(N))[3:]
    stack = []
    count = [0]
    for i in s:
        if int(i) == 0:
            stack.append(i)
        else:
            count.append(len(stack))
            stack = []

    return max(count)

• 이진수는 앞에 '0b' 가 붙기 때문에 슬라이스처리해줍니다. 맨 앞 1도 필요없기 때문에 같이 제거했습니다.
• count 배열에 0 을 넣어둬서 32 처럼 00000 이 처리되지 않는 경우를 미리 초기화해줍니다.
• count 에서 가장 큰 수를 리턴해주면 정답이 됩니다.