Codility -1 Binary gap(Java)

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

 

 

10진수 N의 2진수를 확인하여, 양끝이 1로시작하고 1로 끝나는 binary gap사이에 있는 0의 갯수 구하기.

 

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.

 

내 코드

class Solution {
    public static int solution(int N) {
        int result = 0;
        int biCut = 0;
        String bi = Integer.toBinaryString(N);
        
        int[] arrNum = new int[bi.length()];
        //1) N을 2진수로 바꾸고 각 2진수를 배열에 담는다.
        for (int i = arrNum.length - 1; i >= 0; i--) {
            arrNum[i] = N % 2;
            N = N / 2;
        }
        
        //2) binaryGap 탐색
        for (int i = 0; i < arrNum.length; i++) {
                if (arrNum[i] == 1) {
                    for (int j = i + 1; j < arrNum.length; j++) {
                        if (arrNum[j] == 0) {
                            biCut = biCut + 1;
                            if (j == arrNum.length - 1 && arrNum[j] == 0) { //0값으로 끝날경우 bitCut을 0으로.
                                biCut = 0;
                                if (i == 0) { //0값으로 끝날경우 bitCut을 0으로.
                                    result = biCut;
                                }

                            }
                        }

                        if (biCut > result) { //각 binaryGab 시행마다 가장 큰 값을 result에 보관.
                            result = biCut;
                        }
                        
                        if (arrNum[j] == 1) {
                            i = j - 1; // for에서 i++을 하기 때문에.
                            j = arrNum.length;
                            biCut = 0;
                        }  
                       
                    }
                   
                }
            }
                
           
        // 3) 결과 반환
        return result;
  }
}

 

베스트 코드

 - 핵심은 for문이 1을 만날 때, binaryGap의 수를 어떻게 처리할지임.

    public static int solution(int N) {
        
        ArrayList<Integer> binaryNumList = new ArrayList<>();
        
        while (N > 0) {
            binaryNumList.add(N % 2);
            N /= 2;
        }
        
        int binaryNumListSize = binaryNumList.size();
        int cntBinaryGap = 0;
        int maxBinaryGap = 0; //last return value
        
        for (int i = binaryNumListSize - 1; i >= 0; i--) {
            if (binaryNumList.get(i) == 1) {
                maxBinaryGap = maxBinaryGap(cntBinaryGap, maxBinaryGap);
                cntBinaryGap = 0;
            } else {
                cntBinaryGap++;
            }
            
        }
        return maxBinaryGap;
    }
    
    private static int maxBinaryGap(int cnt, int max) {
        if (max < cnt) {
            return cnt;
        }
        return max;
    }
}

( https://jjjayyy.tistory.com/78 ) 

 

* 필요개념

 - 10진수 2진수 변환 : String a2 = Integer.toBinaryString(num);

 - ArrayList사용

 - 함수로 코드 더 깔끔하게 만들기.