codility, binary gap 문제 풀이

안녕하세요. yeTi입니다.
오늘은 codility에서 제공하는 샘플 문제인 binary gap을 풀어보고 결과를 공유하고자 합니다.

문제

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.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

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

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

        N is an integer within the range [1..2,147,483,647].

Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited. 

문제의 요지는 양의 정수를 바이너리로 표현한 값의 1과 1사이의 간격을 구하는 것입니다.

제가 푼 풀이는 다음과 같습니다.

// Solution.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) {
        int gap = 0;

        String binaryString = Integer.toBinaryString(N);
        char[] binarys = binaryString.toCharArray();
        List<Integer> positions = new ArrayList<>();
        for (int i = 0; i < binarys.length; i++) {
            char binary = binarys[i];
            if (binary == '1') {
                positions.add(i);
            }
        }

        if (positions.size() > 1) {
            for (int i = 0; i < positions.size()-1; i++) {
                int tmpGap = positions.get(i+1) - positions.get(i) - 1;
                if (gap < tmpGap) {
                    gap = tmpGap;
                }
            }
        }

        return gap;
    }
}

풀이의 컨셉은 1의 위치를 모두 판별한 후, 각 위치의 차를 가져오는 것입니다.

추가적으로 테스트할 데이터를 입력해 봤습니다.

// test-input.txt
1
100

테스트 결과는 다음과 같이 성공으로 뜹니다.

// Test Ouput

Compilation successful.

Example test:   1041
OK

Example test:   15
OK

Example test:   32
OK

Your test case: [1]
Returned value: 0

Your test case: [100]
Returned value: 2

Your code is syntactically correct and works properly on the example test.
Note that the example tests are not part of your score. On submission at least 8 test cases not shown here will assess your solution.

이상 codility의 샘플 문제 풀이였습니다.