[codility] BinaryGap c++

• 문제 설명

 

10진수 N을 2진수로 바꾼 후, 1과 1 사이에 존재하는 0의 개수를 구하는 문제이다.

 

ex, 1001           -> length : 2

    1000010001 ->  length : 4 , 3  -> 이 때는 더 큰 수를 return 한다 -> 4

    10100         -> length : 1

    100000       -> length : 0  -> 1이 하나만 있기 때문에 1과 1사이의 0이 없다.

• 문제 풀이

1. string 에 2진수 변환 저장

2. 1검사해서 index vector에 저장

3. index vector size가 1이라면 1이 한개라는 뜻이므로 return 0

4. index vector 에 1의 index가 저장되어 있기에 각 index에 빼기 연산을 하여 Binary Gap을 구한다.

5. max 함수를 이용하여 최댓값만 저장하도록 했다.

 

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <limits>

int solution(int N) {
	// write your code in C++14 (g++ 6.2.0)


	//std::vector<int> vecBinary;
	std::string strBinary("");

	int n = N;
	while (n > 0) {

		int nRes = n % 2;
		n = n / 2;
		strBinary += std::to_string(nRes);
	}

	std::reverse(strBinary.begin(), strBinary.end());

	std::vector<int> vecIndex;
	int nResult = INT8_MIN;
	int count = 0;

	for (int i = 0; i < strBinary.size(); i++) {
		if (strBinary[i] == '1')
			vecIndex.push_back(i);
	}

	if (vecIndex.size() == 1)
		return 0;

	for (int i = vecIndex.size()-1; i > 0; i--) {
		count = vecIndex[i] - vecIndex[i-1] - 1;
		nResult = std::max(count, nResult);
	}

	return nResult;
}


#define BinaryGap

#ifdef BinaryGap

int main() {

	int N1 = 32; // result = 0
	int N2 = 9; //result = 2;

	std::cout << solution(N1);

	return 0;
}

#endif

 

• 결과