★ [2] 2개 이하로 다른 비트 (비트 연산)

문제 설명
양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
예를 들어,

f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
수 비트 다른 비트의 개수
2 000...0010
3 000...0011 1
f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
수 비트 다른 비트의 개수
7 000...0111
8 000...1000 4
9 000...1001 3
10 000...1010 3
11 000...1011 2
정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ 1015

입출력 예
numbers result
[2,7] [3,11]

---

문제 풀이

 

처음에 비트 연산자를 사용해서 풀 생각 안하고 비트를 string 으로 저장한 다음에 +1씩 증가하면서 2개 이하 비트가 차이나는 숫자를 구하려고 했다.

#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <map>

using namespace std;

map<long long, string> cache;
vector<long long> answer;
string IntToBinary(long long num) {
	if (cache.find(num) != cache.end())
		return cache[num];
	cache[num] = bitset<32>(num).to_string();
	return cache[num];
}

int countDifferences(string str1, string str2) {
	return count_if(str1.begin(), str1.end(),
		[&str1, &str2, index = 0](char c) mutable
		{
			return c != str2[index++];
		});
}

void GetAnswer(long long num)
{
	string bit = IntToBinary(num);
	while (true)
	{
		num++;
		string compareBit = IntToBinary(num);

		// 비트가 다른 지점이 2개 이하면 탈출
		if (countDifferences(bit, compareBit) <= 2)
		{
			answer.push_back(num);
			break;
		}
	}
}

vector<long long> solution(vector<long long> numbers) {

	for (int i = 0; i < numbers.size(); i++)
		GetAnswer(numbers[i]);

	return answer;
}

 

결과는 9, 10번 시간 초과

모르겠어서 찾아봤는데 짝수일 때는 +1 만 하면 되고

 

홀수 인 경우.

input data를 2진수 변환했을때 가장 먼저 나오는 0의 자리를 1로 나머지는 0으로
이 숫자를 input data에 더하고 이 숫자를 /2 한 값을 빼주시면 됩니다.
ex) 5 -> 101 -> 가장 먼저 나오는 0을 탐색(2의 1승자리) -> 101 + 10 - 1 -> 110 ->output data : 6
ex) 3 -> 11 -> 가장 먼저 나오는 0을 탐색(2의 2승자리) -> 11 + 100 - 10 -> 101 ->output data : 5

 

라는 규칙을 적용해서 푸는 문제였다.

 

bitSet 과 비트 연산자를 기억하자

비트 추가하는 경우
newNum |= (1LL << position);

비트 제거하는 경우

newNum &= ~(1LL << position);

 

개선 코드

#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <map>

using namespace std;

vector<long long> answer;
int countBitDifferences(long long num1, long long num2) {
	std::bitset<64> bits1(num1);
	std::bitset<64> bits2(num2);
	return (bits1 ^ bits2).count();  // XOR 연산 후 1인 비트의 개수 반환
}

void GetAnswer(long long num)
{
	// 짝수인 경우는 +1 해주면 된다
	if (num % 2 == 0)
	{
		answer.push_back(num + 1);
		return;
	}

	bitset<64> bit(num);
	long long newNum = num;
	for (int i = 0; i < bit.size(); i++)
	{
		if (bit[i] == 0)
		{
			newNum |= (1LL << i);
			newNum &= ~(1LL << i - 1);
			answer.push_back(newNum);
			break;
		}
	}
}

vector<long long> solution(vector<long long> numbers) {

	for (int i = 0; i < numbers.size(); i++)
		GetAnswer(numbers[i]);

	return answer;
}