[Iteration] BinaryGap

코드에 태클 열렬히 환영합니다.

같이 토론해 봤으면 좋겠습니다.

Lesson 1 Iteration BinaryGap

URL : https://codility.com/programmers/lessons/1-iterations/binary_gap/

바이너리 갭은 양의 정수 N 이내의 수를 이진수로 표현했을 때, 0이 연속으로 등장한 값입니다.

N을 2진수로 표현했을 때 1로 둘러싸인 0의 연속된 최대 갯수를 말하죠.

예를 들어서 숫자 9를 보면, 이진수 표현은 1001 이구요, 이때 바이너리 갭은 2입니다.

1로 둘러싸인 구간에서 0이 연속으로 두 번 나왔으니까요.

양의 정수 N이 주어졌을 때 그 수의 바이너리 갭을 반환하는 함수를 작성해봅시다.

예를 들어, 1041이 N으로 주어지면 5를 반환해야 합니다.

1041의 이진수 표현은 10000010001이고 여기서 가장 큰 바이너리 갭의 길이는 5니까요.

제약 조건

- N은 1~2,147,483,647 의 값을 가집니다.

- 최악의 경우 시간 복잡도는 O(log(N)) 입니다.

- 최악의 경우 공간 복잡도는 O(1) 입니다.

C언어 100%점수 획득 코드

int solution(int N) {

int max = 0, cnt = 0, start = 0, i;

for (i = 0; N > 0; i++) {

if (N%2 == 1) {

start = 1;

if (max < cnt) {

max = cnt;

}

cnt = 0;

}

else if (start) {

cnt++;

}

N/=2;

}

return max;

}

2진수는 2로 나눈 나머지를 누적시켜 구하죠.

제일 처음 나누어 나온 나머지가 첫번째 자리, 나눈 몫을 또 2로 나눈 나머지가 두번째 자리...

이렇게 반복문을 통해 나누어 들어가면 첫째자리부터 알 수 있습니다.

어쨌건, 1과 1사이의 수만을 바이너리 갭으로 취급하기 때문에,

이진수 첫째자리가 0일 경우는 바이너리 갭이 성립하지 않습니다.

그래서 맨 처음 1이 나오는 시점부터 0의 갯수를 세도록 start라는 변수를 추가했습니다.

1이 등장할 때 이 값은 1이 됩니다.

또 1이 등장하면 이전 1 등장 시점부터 0이 몇개나 있었는지 cnt 변수를 통해 확인합니다.

이 값을 변수 max와 비교해서 여태 나왔던 바이너리 갭보다 클 경우 그 값을 저장하구요.

그리고 새롭게 0의 갯수를 세기 위해 cnt를 0으로 초기화 해줍니다.

마지막으로 N을 2로 나눠주고 for문에서 조건변화식(N>0)을 확인하여 반복 여부를 결정합니다.

N이 1이면 1/2 = 0 이니까 반복문을 탈출해서 max 값을 리턴합니다.

쉬운 문제이긴 한데, 제가 짠 것보다 간단하게 짤 수도 있을겁니다.

더 파격적인 방법을 아시는 분은 한 수 가르쳐주십쇼.