BinaryGap

19/06/2019 #Codility

해봐야지 해봐야지 하면서 미루다가 Codility가입하고 Lessons에 들어갔다.

전부 영어라 뭐가 뭔지 몰랐지만 일단 Lesson 1을 시작했다. Start 버튼을 누르니 b1 화면이 딱! 뭔가 정말 시험을 보는 느낌이라서 선뜻 시작버튼을 누르기 망설여졌다.

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–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

영문으로 된 지문을 구글 번역을 통해서 번역을 하면

양의 정수 N 내의 이진 갭은 N의 이진 표현에서 양 끝의 것들로 둘러싸인 연속적인 0의 임의의 최대 시퀀스이다.

예를 들어, 숫자 9는 2 진 표현 1001을 가지며 길이 2의 2 진 갭을 포함합니다. 숫자 529는 2 진 표현 1000010001을 가지며 2 개의 2 진 갭 (길이 4와 길이 3 중 하나)을 포함합니다. 숫자 20은 2 진 표현 10100을 가지며 하나의 이진 갭은 길이 1이다. 숫자 15는 이진 표현 (1111)을 갖고 이진 갭을 갖지 않는다. 숫자 32에는 2 진 표현 100000이 있으며 2 진 틈이 없습니다.

함수를 작성하십시오.

클래스 솔루션 {public int solution (int N); }

양의 정수 N이 주어지면 가장 긴 바이너리 갭의 길이를 반환합니다. N이 바이너리 갭을 포함하지 않으면이 함수는 0을 리턴해야한다.

예를 들어, N = 1041이 주어지면 함수는 5를 리턴해야합니다. N은 2 진 표현 10000010001을 가지므로 가장 긴 2 진 갭의 길이는 5입니다. N = 32 일 때 함수 N은 2 진 표현 ‘100000’을 가지므로 0을 반환해야합니다. 바이너리 갭이 없다.

다음 가정에 대해 효율적인 알고리즘을 작성하십시오.

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

10수를 2진수로 만들고 1과 1사이의 0의 개수를 구해서 가장 많은 0의 개수를 리턴하는 코드를 작성하라고 이해했다.

코드

코드는 아래와 같이 작성했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int solution(int N) {
    int answer = 0;
    String result = "";
    if(N > 2147483647){
        return answer;
    }
    while(true){
        result = N % 2 + result;
        N = N / 2;
        if(N == 0){
            break;
        }
    }
    char[] arr = result.toCharArray();
    int cnt = 0;
    for (int i = 0; i < arr.length; i++) {
        if(arr[i] == '1'){
            if(answer < cnt ){
                answer = cnt;
            }
            cnt = 0;
        }else if(arr[i] == '0'){
            cnt += 1;
        }
    }
    return answer;
};
cs

b2