[코딜리티/Java] BinaryGap

입력받은 int값을 2진수로 변환 후 1과 1 사이 길이를 모두 찾아서 제일 길이가 긴 길이를 반환하도록 하는 문제.

이 문제는 시간제한이 따로 없길래 아래와 같이 (좀 무식하게) 이중 for문으로 처리하도록 구현하였다.

class Solution {
    public int solution(int N) {
        int result = 0;
        // 2진수로 변환
        String binaryString = Integer.toBinaryString(N);
        for (int i = 0; i < binaryString.length(); i++) {
            // i번째가 1인 경우
            if (binaryString.charAt(i) == '1') {
                // i+1부터 다시 for문을 돌면서
                for (int j = i + 1; j < binaryString.length(); j++) {
                    // j번째가 1인 경우
                    if (binaryString.charAt(j) == '1') {
                        // 길이를 result와 비교해서 할당
                        result = Math.max(result, j - i - 1);
                        // i를 현재 j값보다 1 작은 값으로 할당하고 break
                        i = j - 1;
                        break;
                    }
                }
            }
        }
        return result;
    }
}

좀 서칭해보니 아래와 같이 먼저 1의 index를 List에 모두 담아두고, 그 List를 loop하면서 길이 계산하는 방식도 있었다.

아래 코드가 더,, 효율적이고 깔끔한 거 같다.

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;
    }
}