BinaryGap (이진 갭)

양의 정수 N의 이진수 표현에서, 양쪽이 1로 둘러싸인 연속된 0들의 구간(더 이상 양쪽으로 확장할 수 없는 구간)을

이진 갭(binary gap) 이라고 한다. 예를 들어,

• 9의 이진수는 1001이며 길이 2의 이진 갭을 하나 포함한다.
• 529의 이진수는 1000010001이며 길이 4와 길이 3의 이진 갭 두 개를 포함한다.
• 20의 이진수는 10100이며 길이 1의 이진 갭을 하나 포함한다.
• 15의 이진수는 1111이며 이진 갭이 없다.
• 32의 이진수는 100000이며 이진 갭이 없다. (끝이 0으로만 이어져 1로 닫히지 않기 때문)

다음 함수를 작성하라:

 

class Solution { public int solution(int N); }

이 함수는 양의 정수 N이 주어졌을 때, 가장 긴 이진 갭의 길이를 반환해야 한다. 만약 N에 이진 갭이 없으면 0을 반환한다.

예를 들어, N = 1041일 때 N의 이진수는 10000010001이므로 가장 긴 이진 갭의 길이는 5이며, 함수는 5를 반환해야 한다. N = 32일 때는 이진수 표현이 100000이므로 이진 갭이 없어 0을 반환해야 한다.

다음 가정을 만족하는 효율적인 알고리즘을 작성하라:

• N은 [1..2,147,483,647] 범위의 정수이다.

 

public class BinaryGap
{
    public int solution(int N)
    {
        // <문제>
        // BinarayGap => 이진수에서 "1과 1 사이"에 낀 0들의 길이.
        // 입력받은 정수를 이진수로 바꿨을 때, 바이너리 갭의 최대 길이를 반환해라.
 
        // 마지막이 0으로 끝나면 오른쪽에 1이 없어 닫히지 않은 구간이다.
        // 1로 끝날 때까지 오른쪽 끝의 0들을 버린다.
        while (N > 0 && (N & 1) == 0)
            N >>= 1; // 오른쪽으로 1칸 민다.
 
        int maxGap = 0;    
        int currentGap = 0;
 
        // 이제 끝이 1이 되었으니, 1과 1 사이의 0들을 세면 됨
        while (N > 0)
        {
            // 현재 오른쪽 끝자리 버리기
            N >>= 1;
 
            // 현재 끝자리가 0이면 아직 1로 안닫힌것.. 
            if ((N & 1) == 0)
            {
                //Gap 에 추가
                currentGap++;
            }
            else
            {
                // 현재 끝자리가 1이면 닫힌 것.
                // maxGap과 현재Gap 비교한다.
                if (currentGap > maxGap)
                    maxGap = currentGap;
 
                // 다음 gap을 세야되므로 초기화
                currentGap = 0;
            }
        }
 
        // 루프가 끝났다는 건 더 이상 왼쪽에 1이 없다는 뜻.
        // 따라서 마지막에 계산하던 currentGap은 오른쪽에 1로 닫히지 않은 구간이므로 무시한다.
       
        return maxGap;
    }
 
}