codility - binary gap python
문제 설명 : binary gapA 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].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited. |
출처 : https://app.codility.com/programmers/lessons/1-iterations/binary_gap/
첫 번째 문제 풀이(정답)
문제는 정수 N을 이진 수로 표현하고 1로 감싸져 있는 0의 개수 중에서 제일 큰 값을 반환하는 것입니다.
예시를 잘 읽어보면 100000 인 경우에는 1로 감싸져 있지 않기 때문에 0을 반환합니다.
10000010001의 경우에는 1로 감싸져 있는 0의 개수들은 5와 3으로 가장 큰 값인 5를 반환합니다.
[1] 우선 N의 정수를 bin()를 사용해 이진수로 표현합니다.
- bin을 사용시에 0b로 시작하는 문자열로 반환됩니다. [2:] slice하여 이 값을 이용합니다.
[2] enumerate()를 이용해 1의 위치인 인덱스를 추출합니다.
- 10000010001의 경우에는 one_index = [0, 6, 10]
[3] 1의 인덱스에서 두 개씩 비교를 합니다. 두 개를 빼고 1을 더하면 0의 개수를 셀 수 있습니다.
- one_index[1] - one_index[0] - 1 = 5
- one_index[2] - one_index[1] - 1 = 3
[4] 위의 값에서 max()를 사용해서 큰 값을 반환하면 문제는 끝입니다.
def solution(N):
# write your code in Python 3.6
# binary gap은 N을 2진수로 표현하고 연속적인 0이 나타내는 값을 카운트한다.
# 단 문제는 1로 감싸줘 있다는 것을 확인해야 한다.
# [1] 2진수로 표현하자. bin()
binary = bin(N)
str_binary = binary [2:]
#print(str_binary) # 10000010001
# [2] index와 value를 확인해보자. 1이 어느 인덱스에 있는 지 확인한다.
one_index = []
for index, value in enumerate(binary):
if value == '1':
one_index.append(index)
# print(one_index) // [0, 6, 10]
# [4] 1의 인덱스를 기반으로 앞의 값과 뒤의 값을 빼고 1을 더하여 계산한다.
binary_gap = []
binary_gap.append(0)
for idx in range(len(one_index)-1):
binary_gap.append(one_index[idx+1] - one_index[idx] - 1)
return max(binary_gap) |
regex 모듈을 통한 통한 풀이
def solution(N):
binary = str(bin(N).split('b')[1])
one_index = [m.start() for m in re.finditer('1', binary)]
# print(one_index) # [0, 6, 10]
result = 0
for i in range(len(one_index) - 1):
result = max(result, one_index[i+1] - one_index[i] - 1)
return result |
다른 사람 풀이
100000의 감싸져여 있지 않은 경우 제거하는 방법은 strip()을 사용하는 것입니다.
양 앞쪽과 끝 쪽의 0을 제거합니다. 마찬가지로 1도 깔끔하게 제거하고, 1로 split()을 하면
0만 아름답게 남겠죠.
100000100010000의 경우를 예로 들어서 밑의 코드를 설명해보면
N = bin(N)[2:]
N = N.strip(‘0’) # 10000010001
N = N.strip(‘1’) # 000001000
N = N.split(‘1’) # [‘00000’, ‘000’]
max(N) = 5
def solution(N):
return len(max(bin(N)[2:].strip('0').strip('1').split('1'))) |
