C++) 프로그래머스 문제 풀이_다음 큰 숫자

 

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

 

첨엔 규칙을 찾아보려고 발버둥을 쳤는데..

....

그저 n+1부터 N과 1 갯수가 같은 수가 나올 때 까지 전부 탐색하면 되는 문제였다.

 

다만 탐색하는 방법을 좀 더 효율적으로 할 수 있을 것 같은데, 그게 영 안돼 ㅠ ;

범위라도 줄여서 구현했다.

원래는 n+1이라도 제외할까 했는데, 생각해보니 1의 다음 큰 숫자는 2라서 걍 패스.

하나 덜 본다고 줄일 수 있을 리도 없고.

 

#include <string>
#include <vector>

using namespace std;

int main() {
	int answer = 0;

	int input ;
	scanf("%d", &input);
	int size_1_inp = 0;
	int size_binary = 0;
	int inp = input;
	for (int i = 0; i < 30; ++i)
	{
		if (inp % 2 == 1) size_1_inp++;
		inp = inp / 2;
		if (inp == 0)
		{
			size_binary = i;
			break;
		}
	}

	int max_value = 1;
	for (int i = 0; i < size_binary; ++i)
	{
		max_value *= 2;
	}

	for (int i = input+1; i <= input + max_value; ++i)
	{
		int outp = i;
		int size_1_out = 0;
		for (int j = 0; j < 30; ++j)
		{
			if (outp % 2 == 1) size_1_out++;
			outp = outp / 2;
			if (outp == 0) break;
		}

		if (size_1_inp == size_1_out)
		{
			answer = i;
			break;
		}
	}
	printf("%d", answer);
}