[Codility] Lesson 1 - JAVA

문제

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

 

문제 해설

solution(int N)에 입력되는 정수의 범위는 1 ~ 2,147,483,647이다.
N으로 입력된 값을 2진수로 변환해준다.
    ex) N : 9 → 1001
          N : 529 → 1000010001
          N : 20 → 10100
          N : 15 → 1111
          N : 32 → 100000

이때 1과 1 사이의 Gap을 계산한다.
(다른 말로 하면 1과 1사이의 0의 갯수를 구해도 된다.)
    ex) N : 1001 → Gap : 2
          N : 1000010001 → Gap : 4, 3
          N : 10100 → Gap : 1
          N : 1111 → Gap : 0
          N : 100000 → Gap : 0

계산된 Gap 중에서 가장 큰 값을 반환한다.

 

풀이 - 1

import java.util.ArrayList;
import java.util.List;
class Solution {
    public int solution(int N) {
        String binaryNum = getBinaryNum(N, "");	
        String regAllOneOrZero = "^0+$|^1+$|^1+0+$";
        if(binaryNum.matches(regAllOneOrZero)) {
            return 0;
        } else {
            List<Integer> idxList = getOneIndex(binaryNum);
            int max = 0;
            for(int i=0; i<idxList.size()-1; i++) {
                max = Math.max(max, (idxList.get(i+1) - idxList.get(i)));
            }
            return max-1;
        }
    }
    
    // 10진수를 2진수로 바꾸기
    public String getBinaryNum(int a, String binaryNum) {
        if(a < 2) binaryNum = a + binaryNum;
        else {
            int div = a / 2;
            binaryNum = (a % 2) + binaryNum;
            binaryNum = getBinaryNum(div, binaryNum);
        }
        return binaryNum;
    }
    
    // 숫자 1이 있는 Index 번호 구하기
    public List<Integer> getOneIndex(String binaryNum) {
        List<Integer> idxList = new ArrayList<Integer>();
        for(int i=0; i<binaryNum.length(); i++) {
            if(binaryNum.charAt(i) == '1') idxList.add(i+1);
        }
        return idxList;
    }
}

 

'풀이 - 1'에 대한 회고

 

Integer에 2진수로 변환하는 Method가 있는데 굳이 만들어서 사용한 이유가 뭘까?

'그냥 2진수부터 만들어볼까?'라는 생각이 결국 더 비효율적인 코드를 만들었다.

 

괜히 고생하지 말고 기존에 있는거 잘 가져다 쓰면 조금 더 코드를 간결하게 작성할 수 있을텐데...

 

코드를 작성할 때 Java에서 지원하는 기능이 있는지 먼저 알아보고

그 다음에 내가 생각한대로 코드를 작성하도록 습관을 길러야겠다.

 

 

풀이 - 2

import java.util.ArrayList;
import java.util.List;
class Solution {
    public int solution(int N) {
        String binaryNum = Integer.toBinaryString(N);	
        String regAllOneOrZero = "^0+$|^1+$|^1+0+$";
        if(binaryNum.matches(regAllOneOrZero)) {
            return 0;
        } else {
            List<Integer> idxList = getOneIndex(binaryNum);
            int max = 0;
            for(int i=0; i<idxList.size()-1; i++) {
                max = Math.max(max, (idxList.get(i+1) - idxList.get(i)));
            }
            return max-1;
        }
    }
    
    // 숫자 1이 있는 Index 번호 구하기
    public List<Integer> getOneIndex(String binaryNum) {
        List<Integer> idxList = new ArrayList<Integer>();
        for(int i=0; i<binaryNum.length(); i++) {
            if(binaryNum.charAt(i) == '1') idxList.add(i+1);
        }
        return idxList;
    }
}

 

'풀이 - 2'에 대한 회고

 

앞에서 2진수를 만들기 위해 작성한 Method를 버리고 Integer의 Method를 이용해서 구현해봤다.

그랬더니 Time spent가 57min에서 3min으로 확 줄어들었다.

역시 처음 생각한 코드는 비효율적이다.

 

그러면 여기서 생긴 또 다른 의문!

List를 꼭 사용해야할까?

코드를 더 간결하게 작성할 수는 없을까?

 

두 가지 의문에 대해 조금 더 고민해보고 더 간결한 방법으로 다시 구현해봐야겠다.

어차피 for문을 이용하는 것이기 때문에 굳이 List를 쓸 필요가 없어보인다.

 

풀이 - 3

class Solution {
    public int solution(int N) {
        String binaryNum = Integer.toBinaryString(N);
        String regAllOneOrZero = "^0+$|^1+$|^1+0+$";
        if(binaryNum.matches(regAllOneOrZero)) {
            return 0;
        } else {
            int max = 0, gap=0;
            boolean pre = false;
            for(int i=0; i<binaryNum.length(); i++) {
                char binary = binaryNum.charAt(i);
                if(binary == '0') {
                    gap++;
                    pre = false;
                } else {
                    if(!pre) {
                        max = Math.max(max, gap);
                    }
                    gap = 0;
                    pre = true;
                }
            }
            return max;
        }
    }
}

 

 

'풀이 - 3'에 대한 회고

 

List를 없애면서 for문을 여러번 돌릴 필요가 없어서인지 또 Time spent가 줄었다.

그런데 여전히 for문 안에 if문이 중첩되어 사용되고 있다.

이런 문제를 해결하면 더 좋은 코드가 만들어질 것 같은데.

일단 내가 코드를 작성한 내용은 여기까지!

 

다른 사람이 풀이한 문제를 보며 어떻게 더 개선했는지 확인해보자!

 

다른 사람의 풀이

class Solution {
    public int solution(int N) {
        String binaryNum = Integer.toBinaryString(N);
        int max = 0, gap=0;
        for(int i=0; i<binaryNum.length(); i++) {
            if(binaryNum.charAt(i)=='1') {
                if(gap!=0) // 사이값 구하기
                    max = max<gap ? gap : max;
                gap = 0;
                continue;
            }
            gap++;
        }
        return max;
    }
}

 

'다른 사람의 풀이'를 통한 회고

또 Time spent가 줄어들었다.

처음 코딩했을 때에 비해 확실히 코드가 간결해졌다.

앞서 코딩을 할 때 사용한 pre 변수도 필요없고, for 안에서의 else문 또한 사라졌다.

 

'풀이 - 3'도 처음에 비해 가독성이 많이 좋아지긴 했지만

'다른 사람의 풀이'도 가독성이 매우 좋아서 코드를 보면 쉽게 이해된다!

다만, '다른 사람의 풀이'에는 '100000'이나 '1100', '1111'과 같이 Gap이 0인 2진수들까지 for문을 수행한다.

 

이런 2진수들은 for문을 실행하지 않도록

그동안의 풀이에서 정규식을 이용해 미리 걸러줬다.

(의도는 좋아! 소스코드가 길어질 뿐...)