CodilityのBinaryGapを競プロ未経験が解いてみた

BinaryGapとは

簡単に言うと、２進数の1と１に囲まれた0の数で最大の値を求める問題です。
例えば1000010100010であれば、1と1の間の0の個数は左から4, 1, 3となるので、ここでは4が答えとなります。

正直、自信はありませんが100%のスコア判定をもらうことができました。Pythonのスペシャリストではない割には簡潔に書けたのではないかと思います。

1. Python コード

def solution(N):
    return len(max(str(bin(N)).replace("0b", "").split("1")[:-1]))

Step. 1

str(bin(N))で与えられた１０進数を２進数に変換します。その際に文字列型へ変換も行います。

Step. 2

.replace("0b", "")二進数を文字列に変換すると最初にリテラルの0bがくっつきます、これをreplace(,)で削除します。

Step. 3

.split("1")1で文字列を分解し、0だけの配列を作成します。

Step. 4

[:-1]でスライスし、最後の要素を削除します。これは、1000や101000のように最後の0は1で囲まれてるとは言えないためです。

Step. 5

str(bin(N)).replace("0b", "").split("1")[:-1]の時点で[0, 00000, 00, 00, 0]のような配列が出来上がります。これをmax( )で文字数(０の数)が一番多い要素を抜き出します。この例だと00000です。

Step. 6

5で00000となったので、len()で0の個数を数えます。この値がBinaryGapの答えとなります。

Java

Javaのバージョンも書いて見ました。Javaはあまり慣れていないので、もっといい書き方があるかもしれません。基本的には上記のPythonと同じアルゴリズムです。
違う点としては与えられる引数Nが割り切れる数か判定している所とPythonではmax()で求められた配列内の最大文字数要素を求めるのを自作している点です。
割り切れるかどうか判定した理由としては1000100101のような文字列を1で分割した際にPythonでは["", "000", "", "00", "", "0", ""]のような配列が帰ってくるので最後の要素を削除することで、必ず１で囲まれた０になることが保証されますが、Javaの場合は[, "000", , "00", , "0"]のような配列になってしまい1001のような場合に挙動が変わってしまうからです。

class Solution {
    public int solution(int N) {
        String[] zeros = Integer.toBinaryString(N).split("1");
        int index = zeros.length;
        int max = 0;

        /* 割り切れる数かどうかの判定 */
        if (N % 2 == 0) {
            index = index - 1;
        }

        /* 最大値の判定 */
        for (int i = 0; i < index; i++) {
            if (zeros[i].length() > max) {
                max = zeros[i].length();
            }
        }

        return max;
    }
}

まとめ

今回は、アルゴリズムプログラミングに初めてトライしました。今後はCodilityの他のLessonやJava(2019/4/6追記)などでもトライしていこうと思います.