Codility - Binary Gap 풀이 (java8)
Codility - Binary Gap 풀이
문제
1) Integer N이 입력된다.
2) 입력받은 Integer 를 binary representation 으로 표현했을때 (529 => 1000010001 )
3) '1' 과 '1' 사이에 있는 '0' 의 최대 길이를 구하라
4) '10000' 의 경우 length는 0 이다 (반드시 '1' 과 '1' 사이의 Gap 만 유효하다)
주의점
1) Input 값의 범위는 1~ 21억 정도의 값이 입력된다.
-> 0인 경우는 없다고 치면 되겠다
-> Integer 범위의 최대크기의 양수가 입력되는 구나
-> 음수는 입력되지 않는다.
2) '1' 과 '1' 사이의 '0' 길이 재기
-> 임의 N을 32bit 로 표현하면 00000000000001000000010000000000 이런식이다.
-> 좌우 양끝 '0'은 의미없는 숫자이므로 계산에서 예외해야한다
풀이
1) binary representation 하는 방법
-> toBinaryString 같은 util을 사용해서 char 배열로 바꾼다
다르게 해보려고한다
이유는 char 배열로 바꾸면 16 bit *31 만큼의 공간을 써야하기 때문이다
그리고 util 내부에서 더 다양한 연산을 할 것이기에 속도측면에서도 불리할 것이다.
-> 0011 & 0001 = 0001
0010 & 0001 = 0000 이기 때문에
-> if((i & N) == i) 이 True 이면 해당 자리수는 1이다.
-> 0001 이라고 하는 비교인자는 0001 << 1 하게되면 0010 이된다.
(문제풀때는 반대로했음 1000에서 내려가는 형태로)
따라서 for문돌면서 >> 해주면 모든 bit를 자리수를 옮겨가며 확인가능하다.
2) '0' 길이 재기
-> 10000 의 gap 은 0이다
오른쪽부터 '0', '1' 체크를 할 경우 10000 의 0의 갯수가 4개가 된다.
왼쪽부터 '0', '1' 체크 하고 결과 반영은 '1'을 만났을때 처리한다.
코드
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N) {
int result = 0;
int checker = 1<<30; // 01000000000000000000000000000000
int count = 0;
while(checker > N) { // N에 근접할때까지 shift
checker = checker >> 1;
}
for(int i = checker; i > 0; i=i>>1){
if((i & N) == i){ // 1이면
if(result < count){
result = count; // 값반영
}
count = 0; //초기화
} else { // 0 이다
count++; // 카운팅 늘리기
}
}
return result;
}
}