[Codility] 1. BinaryGap

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:

class Solution { public int solution(int 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–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

영어공부도 같이 할 겸(?) 최대한 번역기를 돌리지 않고 해보기로 했다.

 

대충 이해한 바로는

자연수 N이 주어졌을때 해당 N을 이진법으로 변환하고, 이진법 표기 내에서 0이 연속되는 최대 카운트 수를 리턴 하라는 것 같다.

단, 1과 1 사이에 있는 0만 해당 되고, 해당 조건에 부합하지 않는 수는 0을 리턴한다.

- 예시(자연수 - 이진표기 - 0갯수)

529 - 1000010001 - 4

20 - 10100 - 1

15 - 1111 - 0

32 - 100000 - 0

1041 - 10000010001 - 5

 

 

나는 이렇게 풀었다.

우선 주어진 자연수 N을이진법으로 변환해야 했다.

N을 0이 될때까지 2로 계속 나눈 후 나머지를 연달아 붙이고

해당 수를 역순으로 정렬하면 이진법 표기가 된다.

 

나는 리스트를 만들어서

나머지들을 리스트안에 넣었고 마지막에 해당 리스트를 reverse 시켜줬다.

 

리스트를 루프 돌면서

0인 경우 카운트를 증가시키고, 1인 경우 리턴값에 현재까지 최대 카운트 수를 담아두고,

그 다음 최대 카운트를 구하기 위해 카운트를 0으로 초기화해 주었다.

단, 1인 경우에 한해서

현재까지 카운트한 0의 갯수가 리스트 총 사이즈를 2로 나눈것보다 길다면, 앞으로 나올 0의 갯수 최대 카운트는 현재 카운트를 넘을 수 없기 때문에 루프를 벗어나게끔 했다.

 

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int N) {
        // write your code in Java SE 8
        
        List<Integer> arr = new ArrayList<>();
        int result = 0;
        int cnt = 0;

        while(N != 0){
            arr.add(N%2);
            N = N/2;
        }
        Collections.reverse(arr);

        for(int i=1;i<arr.size();i++){
            if(arr.get(i) == 0){
                cnt++;
            }else{
                if(cnt >= arr.size()/2 ){
                    result = cnt;
                    break;
                }else{
                    result = (result > cnt) ? result : cnt;
                    cnt = 0;
                }
            }
        }

        return result;
    }
}

 

N이 0이 되기 전까지 while문을 돌면서

N을 2로 나눈 나머지 값을 arr에 담았고

그다음 계산을 위해 N에는 N을 2로 나눈 몫을 다시 담아주었다.

 

다 담은 후 Collections를 이용해 arr 를 reverse 시켜주었고,

 

위에서 말한것처럼 for문을 돌면서 cnt를 계산했다.

for문의 i를 1로 한 이유는

이진법 표기의 첫 숫자는 무조건 1이기 때문에 0번째 요소는 배제하도록 하였다.

 

그리고 결과는 통과.

 

 

내가 푼 방식이 맞는지 피드백을 받아보고 싶어서

다른 분들이 푼 방식들도 참고하였는데

가장 인상깊었던 것은 Integer 에서 제공하는 Integer.toBinaryString을 이용해서

바로 2진 변환된 문자열을 얻어 활용한 방식이었다.

그 후 로직은 나는 리스트에서 요소를 보고 카운트했다면

문자열에서는 각 문자들을 비교해서 카운트 하는 방식이었다.

 

숫자가 주어져서 숫자로만 생각하였는데

이렇게도 생각할 수 있구나 하는 생각이 들었다.

 

아직 멀었다.