[코딜리티] Binary Gap

코딜리티 프로그래머 첫 번째 Lesson 문제인 BinaryGap 은 정수 10진수를 2진수로 변환한 후 1과 1 사이 0의 갯수를 구하고 그 중 가장 많은 0의 개수를 구하는 문제입니다.

예를 들어, 10진수 1041을 2진수로 변환하면 1000010001이 되는데 첫 번째 1과 1사이에 0의 개수는 5개이고, 두번째 1과 1사이의 0의 개수는 3개입니다.

이중 첫번째 1과 1사이의 갯수가 5개로 가장 많으므로 이 숫자를 구하면 되는 문제입니다. (만약 15처럼 2진수가 1111 이면 0이 나오면 됩니다.)

java와 php 코드로 작성했습니다. 

1. java integer 클래스를 이용하는 방법.

// 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
        String binaryString = Integer.toBinaryString(N);
        
        char[] binaryChar = binaryString.toCharArray();
        int totalGapLength = 0;
        int gapLength = 0;
        
        for(int i=0;i<binaryChar.length;++i){
            if(binaryChar[i] == '1'){
                if(gapLength > totalGapLength) totalGapLength = gapLength;
                gapLength = 0;
            }else{
                ++gapLength;
            }
        }
        
        return totalGapLength;
    }
}

- 자바의 Integer 클래스의 toBinaryString 메소드를 활용했습니다. 

- 루프를 돌리면서 2진수의 값이 1이 아닐경우에는 gapLength 변수의 크기를 1씩 증가 시켜줍니다.

- 2진수의 값이 1일때는 gapLength 변수의 값을 기존 totalGapLength 변수의 값과 비교하여 totalGapLength보다 클 경우 값을 대입해주고

  gapLength의 값을 0으로 초기화해줍니다. (다시 1과 1사이의 0의 개수를 구하기 위해)

2. java 클래스를 활용하지 않는 방법.

// 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
        int totalGapLength = 0;
        int gapLength = 0;
        
       while(N!=0) {
            N = N/2;
            if(gapLength > totalGapLength) totalGapLength = gapLength;
            if(N%2 == 1) gapLength = 0;
            else           ++gapLength; 
        }
        
        return totalGapLength;
    }
}

- 2진수를 구하는 방법은 10진수를 2로 나눈 나머지 값들을 이용하면 구할 수 있습니다.

- 10진수를 2로 더이상 나눌 수 없을때까지 나누면서 루프를 돌립니다. 그 과정에서 1과 1사이의 0의 개수를 구하면 됩니다.

3. php decbin 함수를 이용한 방법

// you can write to stdout for debugging purposes, e.g.
// print "this is a debug message\n";

function solution($N) {
    // write your code in PHP7.0
    $binary = decbin($N);

    $totalLen = 0;
    $len = 0;
    for($i=0;$i<strlen($binary);++$i){
        if($binary[$i]=='1'){
            if($len > $totalLen) $totalLen = $len;
            $len = 0;
        } else {
            ++$len;
        }
    }
    return $totalLen;
}

- php는 decbin() 이라는 2진수 값을 구하는 함수가 있습니다.  그 외에는 자바와 비슷합니다.

- java와 다른 점은 php는 변수 타입에 영향을 받지 않으므로 자바에서 처럼 char[] 로 받지 않아도 루프를 돌릴 수가 있습니다.

4. php의 decbin 함수를 이용하지 않는 방법은 java와 거의 비슷해서 추가하지 않았습니다.