[codility] 레슨1 BinaryGap

알고리즘 공부를 해야지 해야지 하다가 이제서야 시작.

코딜리티(Codility)라는 좋은 사이트를 접하게 되어서 문제를 풀어보기로 마음먹었다.

코딜리티로 문제를 풀고나면 복잡도(Big-o)도 계산해주고 스코어도 매겨준다.

첫번째 문제.

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:

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.

코딩하는 시간보다 문제 이해하는시간이 더 걸리는 것 같다.

문제는 이러하다.

10진수를 2진수로 변환했을 때 1과1사이의 0의 최대값(cnt)을 구해라.

예를들어 1001 이면 1과 1사이의 0의 개수는 2다.

반면 10001000001은 000 (3)  00000 (5) 로 최대값은 5 다.

풀어서 제출하고나니 스코어가 80%가 나왔다.

기왕하는거 100%위해 재도전.

제출한 풀이.

---

class Solution { public int solution(int N) { // write your code in Java SE 8 String binaryStr = Integer.toBinaryString(N); char[] chrs = binaryStr.toCharArray(); int gap = 0; int result = 0; for(char c : chrs){ if(c=='0'){ ++gap; }else{ if(gap>result){ result = gap; } gap = 0; } } return result; } }

---

Integer.toBinaryString()함수로 입력받은 정수를 2진수(String)으로 변환해주고,

char배열로 다시 변환한다.

char배열을 루프돌려 값이 0이면 gap을 계속 증가시키고,

1이면 result와 비교해 값을 넣어주고 초기화해준다.

루프가 끝나면 result 리턴.

알고리즘 문제는 앞으로 꾸준히 풀어봐야겠다.