BinaryGap (Codility)

 

문제

입력 된 숫자를 이진수로 변환시키고, 변환된 이진수중 1과 1 사이에 있는 0이 가장 많은 경우 0의 갯수를 출력하는 문제이다. (다만 1과 1사이에 있지 않은 0은 포함되지 않는다.)

 

예를들면, 1041 숫자는 이진수로 변환하면 10000010001이다. 1과 1 사이에 있는 0은 앞에 5개, 뒤에 3개가 있다. 그러므로 가장 많은 경우의 5개를 출력하면 된다. 

 

해결 방법

우선 이진수로 변환하는 방법은 이전에 사용하였던 것이다. 

비밀지도 (프로그래머스)

 

 

코드는 다음과 같다.

#include <iostream>
#include <vector>
using namespace std;

string toBinary(int N) 
{
	string result = "";
	// int 최대 범위의 이진수 갯수
	int count = 32, tmp = 1;
	// int 최대 범위부터 내려가며 최초로 1이 나오는 경우 
	// 이진수에서 가장 큰 자리수이다.
	while (true) 
	{
		if(count <= 0 || (N >> count) & 1) break;
		--count;
	}
	// 가장 큰 자리수 부터
	// 1, 0을 구분해 string을 더해나간다.
	for (int i = count; i >= 0; --i)
		((N >> i) & 1) ? (result += '1') : (result += '0');
	return result;
}

int solution(int N) 
{
	string bin = toBinary(N);
	int result = 0, tmp = 0;
	for (const auto iter : bin) 
	{
		// 1이 나온 경우 지금까지
		// 나왔던 0의 갯수를 최대 개수와 비교하여
		// 크다면 갱신한다.
		if (iter == '1')
		{
			if (result < tmp) result = tmp;
			tmp = 0;
		} else 
		{
			++tmp;
		}
	}
	return result;
}