Codility - Binary Gap 풀이 (java8)

Codility - Binary Gap 풀이

문제

1) Integer N이 입력된다.

2) 입력받은 Integer 를 binary representation 으로 표현했을때 (529  => 1000010001 )

3) '1' 과 '1' 사이에 있는 '0' 의 최대 길이를 구하라

4) '10000' 의 경우 length는 0 이다 (반드시 '1' 과 '1' 사이의 Gap 만 유효하다)

 

 

주의점

1) Input 값의 범위는 1~ 21억 정도의 값이 입력된다.

   -> 0인 경우는 없다고 치면 되겠다

   -> Integer 범위의 최대크기의 양수가 입력되는 구나

   -> 음수는 입력되지 않는다.

 

2) '1' 과 '1' 사이의 '0' 길이 재기

   -> 임의 N을 32bit 로 표현하면 00000000000001000000010000000000 이런식이다.

   -> 좌우 양끝 '0'은 의미없는 숫자이므로 계산에서 예외해야한다

   

 

풀이

1) binary representation 하는 방법

    -> toBinaryString 같은 util을 사용해서 char 배열로 바꾼다 

         다르게 해보려고한다

        이유는 char 배열로 바꾸면 16 bit *31 만큼의 공간을 써야하기 때문이다

        그리고 util 내부에서 더 다양한 연산을 할 것이기에 속도측면에서도 불리할 것이다.

 

    -> 0011 & 0001 = 0001

        0010 & 0001 = 0000 이기 때문에

    

    -> if((i & N) == i) 이 True 이면 해당 자리수는 1이다.

 

    -> 0001 이라고 하는 비교인자는 0001 << 1 하게되면 0010 이된다.

        (문제풀때는 반대로했음 1000에서 내려가는 형태로)

        따라서 for문돌면서 >> 해주면 모든 bit를 자리수를 옮겨가며 확인가능하다.

    

 

2) '0' 길이 재기

     -> 10000 의 gap 은 0이다

         오른쪽부터 '0', '1' 체크를 할 경우  10000 의 0의 갯수가 4개가 된다.

         왼쪽부터 '0', '1' 체크 하고 결과 반영은 '1'을 만났을때 처리한다.

코드

// 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) {
        int result = 0;
        int checker = 1<<30; // 01000000000000000000000000000000
        int count = 0;

        while(checker > N) { // N에 근접할때까지 shift
        	checker = checker >> 1;
        }
        
        for(int i = checker; i > 0; i=i>>1){  
            if((i & N) == i){  // 1이면
            	if(result < count){
                    result = count; // 값반영
                }
            	count = 0; //초기화
            } else { // 0 이다
                count++; // 카운팅 늘리기
            }   
        }
        return result;
    }
}