Codility ] Lesson1 : BinaryGap

알고리즘 사이트 : https://app.codility.com/programmers/

안녕하세요.

웹 사이트 내에서 알고리즘 문제를 풀고 오류를 체크 할 수 있는 좋은 사이트가 있습니다.

바로 Codility 사이트 인데요.

아마 개발자라면 다들 한번쯤은 들어 보셨을 거라고 생각합니다!

오늘부터 Codility 사이트에서 시간 날때마다 하나씩 알고리즘을 풀고 공유 하려고 합니다.

제 목표는 알고리즘 문제를 100%로 해결 하는 거예요.

그럼, 이제 금일 해결한 알고리즘 1단계 BinaryGap 을 포스팅 하겠습니다!

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.

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.

Assume that:

• N is an integer within the range [1..2,147,483,647].

Complexity:

• expected worst-case time complexity is O(log(N));
• expected worst-case space complexity is O(1).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

BinaryGap 문제는 주어진 숫자를 2진수로 변경하여 1과 1 사이에 있는 0의 개수가 가장 많은 것을 찾는 거예요.

예를 들어 1000101 가 주어지면 정답은 3, 1001011의 정답은 2 입니다.

예외 사항으로 1과 1 사이에 포함되지 않은 0 값은 무시합니다.

예를 들어 10100000 이라는 2진수가 있다면 정답은 5가 아닌 1이 됩니다!

제가 풀이한 자바 알고리즘 (100%) 입니다.

다 풀고 나서 다른 분들의 풀이를 찾아보니 정말 다양한 방법으로 문제를 푸시더라구요.

제가 풀이한 답이 좋은 알고리즘이라고 할 순 없지만 100%로 통과했으니 참고 하시기 바랍니다!

제가 푼 방법입니다.

1. 들어온 값을 2진수로 변경.

2. 변경된 2진수의 값을 String 배열로 담아 1로 split.

3. split되어 배열에 들어간 값을 for문으로 돌려 새로운 int 배열에 0의 개수를 입력.

4. int 배열을 오름차순으로 정리 후 가장 큰 값 출력.

* 예외 사항 

1. String 배열의 길이가 0이라면 그냥 0을 출력.

2. 들어온 값이 홀수라면 int 배열의 가장 큰 값을 출력, 짝수라면 두번째로 큰 값 출력

import java.util.Arrays; class Solution { public int solution(int N) { // write your code in Java SE 8 String binary = Integer.toBinaryString(N); String return0 = binary.substring(binary.length()-1, binary.length()); String binaryArr[] = binary.split("1"); int Narr[] = new int[binaryArr.length]; int result = 0; //맨 뒤에가 0이면 맨 뒤에 값을 제외하고 값을 담는다. if(return0.equals("0")) Narr = new int[binaryArr.length-1]; for(int i=0; i<Narr.length; i++) { Narr[i] = binaryArr[i].length(); } Arrays.sort(Narr); if(Narr.length == 0) return 0; else return Narr[Narr.length-1]; }  }

import java.util.Arrays; class Solution { public int solution(int N) { String str = Integer.toBinaryString(N); // 2진수로 변환 String strArr[] = str.split("1"); // 1로 split int result[]=new int[strArr.length]; // strArr의 길이를 배열로 담음 if(strArr.length != 0){ // 길이가 0이 아닐 때 실행 for(int i=0; i<strArr.length; i++){ if(i<strArr.length-1){ if(strArr[i].length() < strArr[i+1].length()) result[i] = strArr[i+1].length(); else result[i] = strArr[i].length(); } } Arrays.sort(result); // 오름차순 정렬 if(N%2 != 0) // 홀수라면 가장 큰 값 N = result[strArr.length-1]; else // 짝수라면 두번째 값 N = result[strArr.length-2]; }else{ N = 0; } return N; } }

소스에 문제가 있거나, 더 나은 방향으로 제시해 주시면 너무나 감사하겠습니다.

이상 포스팅을 마치겠습니다.