[Codility(코딜리티)] Lesson1. BinaryGap (100%)

Lesson 1 Iterations - BinaryGap (Java Solution)

https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

BinaryGap coding task - Learn to Code - Codility

문제

10진수 N이 주어진다. 이 N을 이진수로 바꿨을 때,

1과 1사이에 0의 갯수를 센 후, 가장 긴 0의 개수를 출력하는 것이다

 

해결

1. 주어진 10진수 N을 2진수로 바꿔준다 

1-1) java.lang.Integer에서 제공해주는 Integer.toBinaryString(N)을 사용

 

String binaryString = Integer.toBinaryString(N);

 

1-2) 직접 만든다

이진수를 구하는 방법은 10진수 N이 들어왔을 때, N이 0이 될때까지 2로 계속 나눈 후 나머지를 합쳐 거꾸로 돌리면 된다

예를 들면, N=11이면

몫 나머지

11/2 = 5, 11%2 = 1 

5/2 = 2, 5%2 = 1

2/2 = 1, 2%2 = 0

1/2 = 0, 1%2 = 1

-> 1101 -> reverse(1101) -> 1011 (1+2+8) = 11

위 로직을 코드로 표현하면 아래와 같다

private String integerToBinaryStr(int N) {
        StringBuilder builder = new StringBuilder();
        while(N != 0) {
            builder.append(N%2);
            N = N/2;
        }
        return builder.reverse().toString();
    }

String이 아닌 StringBuilder를 사용한 이유는 성능 저하를 피하기 위해서이다

자세한 내용은 아래 링크에 정리해두었다. 시간이 된다면 한번 가볍게 읽어보자

https://jackjeong.tistory.com/10

[이펙티브자바 3판] ITEM 63. 문자열 연결은 느리니 주의하라

 

2. 위에서 구한 2진수 N으로 1과 1사이의 0의 개수 최대값을 구한다 

10진수 11을 2진수로 표현하면 1011이다

1011에서 1을 발견하면 0의 개수를 추가하고, 다시 0의 개수를 0으로 초기화해준다

10000110010101001이 있을 때, list에는 0(초기값:1과 1사이에 0이 존재하지 않을 수도 있음)이 먼저 추가되고 이후에

4, 2, 1, 1, 2가 추가될 것이다. 그리고 여기서 최대값은 4가 된다

 

public int solution(int N) {
        // 2진수 변환 - 1. Integer.toBinaryString()
         String binaryString = Integer.toBinaryString(N);
        // 2진수 변환 - 2. 직접 구현
        //String binaryString = integerToBinaryStr(N);

        List<Integer> numOfZeroList = new ArrayList<>();
        int numOfZero = 0;
        for(char i : binaryString.toCharArray()) {
            if(i=='1') {
                numOfZeroList.add(numOfZero);
                numOfZero = 0;
            } else {
                numOfZero++;
            }
        }
        return numOfZeroList.stream().mapToInt(x->x).max().getAsInt();
    }