[코딜리티/Codility]이진 갭(Binary Gap) 알고리즘

---

---

# 여는 글

안녕하세요, 음냐음 입니다.

여러분들은 코딜리티(Codility)라는걸 아십니까?

저도 우연찮게 코딜리티(Codility)를 알게되었는데,

알고리즘 풀이 사이트입니다.

저도 한번, 풀어봤는데 꽤 괜찮더라구요.

그런의미에서 한번 공유해 보겠습니다.

# 문제

• 양수의 int 형 숫자를 이진수로 표현하였을때 1과 다른 1의 차이(Binary Gap), 즉 1과 다른 1사이의 0의 개수가 최대인 경우를 찾아야 한다.

• 예를들면 9는 이진수로 1001 이니 1과 1사이에 0이 2개가 있어 Binary Gap의 길이는 2이다. 529같은 경우는 이진수1000010001 이며 Binary Gap 은 총 2개인데, 100001의 부분의 4와 1001 부분의 3이다. 이때 최대값은 4이므로 4를 리턴하면 된다.

• 정수의 범위는 1~2,147,483,647 이다.(int형의 양수 최대 표현 범위)

• 복잡도 요구사항(시간복잡도 O(log(N)), 공간복잡도 O(1))

# 코드

// 이진 갭 알고리즘 함수
class Solution {
    public int solution(int N) {
        int result = 0;
        int CurrentBinaryGap = 0;
 
        // 십진수를 이진수로 바꿔주는 함수
        String DecimalToBinary = Integer.toBinaryString(N);
 
        // 이진수를 글자 수 만큼 반복문을 돌린다.
        for(int i = 0; i < DecimalToBinary.length(); i++){
            // 이진수가 0일 때
            if(DecimalToBinary.charAt(i) == '0'){
                CurrentBinaryGap++;
            }else{
                // 이진수가 0이 아니라면 이전 값과 비교(첫번째 일 경우 result는 0이 됨) 
                if(CurrentBinaryGap > result){
                    result = CurrentBinaryGap;
                }
                
                CurrentBinaryGap = 0;
            }
        }
 
        return result; 
    }
}

# 마무리

위 포스트는 제가 직접 제작한 것 입니다.

그렇기 때문에 틀린점이나 설명이 엉성한 점이 존재할 수 있습니다.

만약 틀린점이나 설명이 엉성한 부분이 존재하면 댓글로 알려주세요.

빠른 처리 하도록 하겠습니다.

티스토리 앱으로는 댓글 이용이 불가능 하므로 웹 브라우저로 봐 주세요

(URL : http://junprogramer.tistory.com/)

읽어주셔서 감사합니다.