AlgorithmCodility

Codility Binarygap

,

1. Codility Binary Gap

1.1. 컴퓨팅적 사고

이진수를 활용하여 이진수의 1의 위치에서 가장 최댓값을 구하는 간단한 문제였습니다. 약 20분정도 소요된 문제입니다. 처음에는 Integer.binaryString() 함수를 사용하지 않고 직접 구현을 하였는데, 불 필요해보였습니다. reverse()도 따로해줘야하고 시간복잡도면에서 뛰어나지 않다고 생각을 하게 되었습니다.

  1. N의 값 이진수로 변환합니다.
  2. 이진수로 변환후 1의 위치를 리스트에 저장합니다.
  3. 리스트에 담긴 위치별로 substring을 사용하여 값에 대한 length를 체크하여 최댓값을 구해줍니다.

시간복잡도: O(N)

1.2. 소스코드

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
28
29
30
31
32
33
34
35
36
37
38

public class binaryGap_lesson01 {
    public static void main(String[] args) {
        solution(9);
        solution(1162);
    }
    static int solution(int N) {
        // write your code in Java SE 8
        /* 직접 구현하기 이진수로 변경
        List<Integer> arrList = new ArrayList<>();
                while(N > 0){
                    int div = N % 2;
                    N = N / 2;
                    arrList.add(div);
                }
                Collections.reverse(arrList);
        */
        String binaryStr = Integer.toBinaryString(N);

        int cnt = 0;
        List<Integer> arrList = new ArrayList<>();
        for(int i=0; i<binaryStr.length(); i++){
            if(binaryStr.charAt(i) == '1'){
                cnt++;
                arrList.add(i);
            }
        }
        int answer = 0;
        if(cnt > 0) {
            for (int i = 0; i < arrList.size() - 1; i++) {
                String subStr = binaryStr.substring(arrList.get(i), arrList.get(i+1));
                answer = Math.max(answer, subStr.length()-1);
            }
        }
        //System.out.println("answer = " + answer);
        return answer;
    }
}
Share