다음 큰 숫자(Level2)

• 문제 링크: 코딩테스트 연습 > 연습문제 > 다음 큰 숫자

• 문제 이해

  1. 만약 주어진 수가 A이고, B가 다음 큰 숫자라고 가정합니다.
  2. A를 2진법으로 나타냈을 때와 B를 2진법으로 나타냈을 때 1의 개수는 같습니다.
  3. A와 B를 모두 10진법으로 나타냈을 때, B는 A보다 크며, 위의 조건을 만족시키는
     바로 다음 수가 됩니다.

• 알고리즘 구현

  1. 먼저, 2진법으로 나타냈을 때의 1의 개수를 셉니다. 이 때, 재귀함수를 이용합니다.
  2. brute-force를 이용하여, A + 1부터 문제이해의 2번 조건을 확인하는지 체크하고,
     계속해서 A를 증가시켜나갑니다.
  3. 수가 계속 증가하다, 기존에 입력받은 A와 1의 개수가 같아지면 출력할 때 그 수가
     다음으로 큰 수가 될 것입니다.

• 알고리즘

int refBitNum;

int cntBit(int n) {
    if (n == 0) return (0);
    return (n % 2 + cntBit(n / 2));
}

int solve(int N) {
   if (cntBit(N) == refBitNum) return (N); 
   return (solve(N + 1)); 
}

int solution(int n) {
    int answer = 0;
    refBitNum = cntBit(n);
    answer = solve(n + 1);
    
    return answer;
}