문제

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

풀이 1

// 다음 큰 숫자

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

using namespace std;

int countChar(string s, char c = '1') {
	int count = 0;
	for (char i : s) {
		if (i == c)
			count++;
	}

	return count;
}

int solution(int n) {
	int n_count = countChar(bitset<8>(n).to_string(), '1');
	int answer = 0;

	for (int next_num = n+1; next_num < 1000000; next_num++) {
		string binary_str = bitset<8>(next_num).to_string();
		int next_n_count = countChar(binary_str, '1');

		if (n_count == next_n_count) {
			answer = next_num;
			break;
		}
	}
	
	return answer;
}

int main()
{
	cout << solution(78) << endl; // 83
	cout << solution(15) << endl; // 23
}

• 먼저, bitset을 통해 10진수를 2진수로 바꾼다.
• 그 이후 string 형태로 1의 갯수를 세워주는 함수를 바꾼다.
• 10진수가 입력되면 그 수의 이진수에서 1의 갯수가 같으면서 가장 가까운 수를 반환한다.