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

 

n보다 큰 자연수 중에서, 2진수로 표현했을 때 1의 개수가 n과 같은 숫자들 중 가장 작은 수를 출력하면 된다.

 

문제 풀이

 

문제는 어렵지 않다.

 

n을 2진수로 변환했을 때, 1이 몇개있는지 먼저 구해준다.

 

이후, n을 1씩 증가시키면서 해당 숫자를 2진수로 변환했을 때, 1이 몇개있는지를 구해준다.

 

1의 개수가 n과 같아지는 숫자가 발견되면, 해당 숫자를 반환하면 된다.

 

2진수의 각 숫자들은 10진수를 2로 나누었을 때 나머지이다.

그러므로, 숫자를 0이 될 때까지 계속 나누면서 나머지가 1이 되는 경우가 몇 번 있는지를 구해주면 2진수에 1이 몇개 있는지 구할 수 있다.

 

풀이 코드

 

int GetOneCount(int _Num)
{
    int CurOneCount = 0;
    
    while(_Num > 0)
    {
        if(_Num % 2 == 1)
        {
            CurOneCount++;
        }
        
        _Num /= 2;
    }
    
    return CurOneCount;
}

 

특정 숫자를 2진수로 변환했을 때, 1이 몇개있는지 구하는 함수이다.

위에서 설명했듯이, 계속 2로 나누면서 나머지가 1이 되는 경우가 몇 번 나오는지를 구해주고 있다.

 

int solution(int n) 
{
    int CurOneCount = GetOneCount(n);

    int PlusCount = 1;
    int CurNum = 0;
    
    while(true)
    {
        CurNum = n + PlusCount;
        
        int NextOneCount = GetOneCount(CurNum);
        
        if(NextOneCount == CurOneCount)
        {
            break;
        }
        
        PlusCount++;
    }
    
    return CurNum;
}

 

솔루션도 간단하다.

 

먼저, 처음 주어진 숫자에 대해 1의 개수를 구해준다.

 

이후, 수를 1씩 증가시키면서 1의 개수를 계속 구해주다가 처음 주어진 수와 1의 개수가 동일한 수가 발견되면 해당 수를 반환하면 된다.

 

 

코드 전문

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

using namespace std;

int GetOneCount(int _Num)
{
    int CurOneCount = 0;
    
    while(_Num > 0)
    {
        if(_Num % 2 == 1)
        {
            CurOneCount++;
        }
        
        _Num /= 2;
    }
    
    return CurOneCount;
}

int solution(int n) 
{
    int CurOneCount = GetOneCount(n);

    int PlusCount = 1;
    int CurNum = 0;
    
    while(true)
    {
        CurNum = n + PlusCount;
        
        int NextOneCount = GetOneCount(CurNum);
        
        if(NextOneCount == CurOneCount)
        {
            break;
        }
        
        PlusCount++;
    }
    
    return CurNum;
}