Codility - Binary Gap // C++

문제

 

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. The number 32 has binary representation 100000 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. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..2,147,483,647].

N이라는 정수를 입력 받고, 이진법으로 나타냈을 때 "1" 사이의 "0"의 최대 개수를 구하여라.

 

예를 들어, 9는 이진법으로 1001이므로 1 사이의 0의 최대 개수는 2가 된다.

 

---

 

풀이

먼저, 입력받은 10진수의 정수를 2진수로 나타낸다.

2진수로 변환하는 방법은 1 이하의 수가 될때까지 2로 나누면서, 마지막에 나온 몫을 제일 앞부분에 쓰고 나누는 과정에서 나왔던 나머지를 마지막 과정의 나머지부터 써주면 된다.

 

다음으로 2진수의 수에서 1 사이의 0의 개수를 구하면 되는데,

문제에서 나온 것처럼 32 같은 경우는 2진법으로는 100000가 된다.

1로 시작은 하였으나 끝까지 0만 나왔으므로 이 경우의 답은 0이 된다.

 

문제를 풀 때에는 생각을 못 했었지만 0이거나 2의 n제곱인 경우는 무조건 0이 되고, 나머지 경우에서는 1이 최소한 두개는 나오게 되니까 0 또는 2의 n 제곱인 경우만 예외 처리를 하면 될 것 같다.

 

 

---

 

코드

int soultion(int N){
	string temp_str, str;
	
		while (temp > 1) {
			temp_str += to_string(temp % 2);
			temp /= 2;
		}
		temp_str += to_string(temp);

		for (int i = temp_str.length() - 1; i >= 0; i--) {
			str += temp_str[i];
		}

		int len = 0;
		int max = 0;
		int index = 0;

		while (index < str.length()) {
			if ((index = str.find("1", index)) != std::string::npos) { // 시작할 1의 위치를 찾음
				if ((temp = str.find("1", index + 1)) != std::string::npos) { // 끝날 1의 위치를 찾음
					len = temp - index - 1; // 시작과 끝의 index 차이만큼 길이

					if (len > max)
						max = len;

					index = temp;
				}
				else // 1로 끝나는 경우가 없다면 종료(100000과 같은 경우)
					break;
			}
			else // 아예 1이 없다면 종료(0의 경우)
				break;
		}
        return max;
}