다음 큰 숫자 (프로그래머스) - C++

• 문제

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

• 설명

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

• 풀이

  • 처음에는 숫자를 이진수로 변환한 뒤에, 뒷자리(작은 수)부터 확인하면서 1 다음에 0 이 오면 오버플로우 시킨 후 , 그 전에 있던 1의 갯수만큼 뒷자리부터 채운 후에 오버플로우 된 자리 이전까지 0으로 채우면 된다고 생각했다. 다소 복잡하고 체계적이지 않은 방식이다. 심지어 틀린 방법인 것 같다.
  • 다른 방법으로 생각한 것은 n을 이진수로 변환했을 때 1의 갯수를 카운팅하고, n을++ 하면서 그 수를 2진수로 바꿔서 1의 갯수가 같은지 확인하는 방법을 사용하였다. 코드가 보다 간단해지고 명확해졌다.

#include <string>
#include <vector>
 
using namespace std;
 
int Binary(int num)//이진수의 1의 갯수를 반환
{
    int one_count = 0;
    while(num != 0)
    {
        if(num % 2 == 1)
            one_count++;
        
        num = num / 2;
    }
    return one_count;
}
 
int solution(int n) {
    int answer = 0;
    
    int one_count = Binary(n);//n을 이진수로 변환했을 때 1의 갯수를 입력.
    
    while(true)
    {
        n++;//n을 1씩 증가
        if(one_count == Binary(n))//증가된 n 의 이진수의 1의 갯수와 기존 n의 갯수가 같다면
        {
            answer = n; // answer 을 입력하고
            break; //종료
        }
           
    }
    
    return answer;
}