TIL79. CodeKata : 가장 큰 binary gap 구하기 문제

🌈 가장 큰 binary gap 구하기 문제

🤔 나의 Solution

양수 N을 이진법으로 바꿨을 때, 연속으로 이어지는 0의 갯수가 가장 큰 값을 return해 주세요. 이어지는 0은 1과 1사이에 있는 것을 의미합니다. 이런 것을 binary gap 이라고 합니다.

✔️ 9가 전달되었을 때, 이를 이진수로 바꾸면 1001입니다. 이에 1과 1사이에 있는 0은 2 이므로, 2를 반환합니다.

✔️ 529가 전달되었을 때, 이를 이진수로 바꾸면 1000010001입니다. 이에 1과 1사이에 있는 0은 4와 3 이므로, 4를 반환합니다.

✔️ 20이 전달되었을 때, 이를 이진수로 바꾸면 10100입니다. 이에 1과 1사이에 있는 0은 1 뿐이므로, 1를 반환합니다.

✔️ 32가 전달되었을 때, 이를 이진수로 바꾸면 100000입니다. 이에 1과 1사이에 있는 0은 없기 때문에 0를 반환합니다.

def solution(N):
    N = bin(N)[2:]
    res = N.strip('0').strip('1').split('1')
    return len(max(res))
print(solution(529))

✔️ 양수를 이진법으로 바꾸는 방법은 bin 함수를 이용하면 간편하다. 맨 앞에 0과 알파벳이 붙기 때문에 이를 제거하기 위해 슬라이스 했다.

✔️ 이제 남은 수들 중 0부터 strip해준다. 1과 1사이에 있는 0의 갯수 중 큰 수를 반환하는 문제이기 때문에 이 단계에서 나타나는 0은 갯수를 판단할 필요가 없다.

✔️ 0을 제거했으면 1을 기준으로 strip하여 1과 1사이의 1들을 제거한다. 그리고 1을 기준으로 split하면 0이 연속으로 이어져 리스트에 담기게 된다.

✔️ 예를들어, 592 양수가 전달되면, '0b1000010001'이 상태에서 0b를 지운다음 0을 벗기면 외부에 0이 없기 때문에 "1000010001"이다.

✔️ 여기서 1을 다시 벗기면 "00001000"이기 때문에 이를 1로 split하면 ['0000', '000']이 된다. 여기서 max값의 길이를 반환하면 4가 된다.

🤔 다른 해결 방법

def solution(N):
    N = bin(N)[2:]
    count = 0
    max_count = 0
    for i in N:
      if i == '1':
        if max_count < count:
          max_count = count
          count = 0
        else:
          count = 0
      else:
        count += 1
    return max_count
print(solution(529))

✔️ 529를 이진법으로 바꾼 뒤, 앞에 0b를 때면 "1000010001"이된다. 이를 for문을 통해 순회하여 해결하는 방법이다. 반복문에서는 i는 1,0,0,0,0,1,0,0,0,1 순으로 변화된다.

✔️ 이 때, i가 1이라면 현재 count에 담긴 값과 max_count에 담긴 값을 비교해서 count에 담긴 수가 더 크다면 이를 max_count와 교체한다.

✔️ 왜냐하면 i가 0일 때는 계속 count값에 1을 더해주고, 직전까지 가장 큰 count값이 max_count에 담겨있기 때문이다.

✔️ 즉, 단순하게 순회하면서 가장 큰 값을 max_count에 담아 업데이트시키면서 해결하는 방식이다.