2진수의 1개수가 같은 다음 수 찾기

문제

어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다.

• N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
• 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.
• 예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다.
• N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.

풀이

무식하게 코딩한 방법이긴 한데.. 풀 당시 다른 사람들의 코드를 봐도

현재로선 더 좋은 방법이 떠오르지가 않는다..

코드 자체는 워낙 쉬우니 간단하게 설명하면(너무 직관적이다..)

숫자를 2진수로 변환하고 1 개수를 구한다. 그리고 1씩 더하며 1개수가 같아지는 시점을 반환한다…

#include <iostream>

using namespace std;

int oneCount(int n)
{
  int count = 0;
  while (n != 0)
  {
    count = (n % 2 == 1) ? ++count : count;
    n /= 2;
  }
  return count;
}

int nextBigNumber(int n)
{
  int answer = n;

  int nOne = oneCount(n);
  while (1)
  {
    ++answer;
    if (oneCount(answer) == nOne)
      break;
  }

  return answer;
}
int main()
{
  int n = 78;

  // 아래는 테스트 출력을 위한 코드입니다.
  cout << nextBigNumber(n);
}

먼저 들어온 숫자(78)의 1의 개수를 계산한다. 4라는 값이 반환될 것이고, 이 값을 임시 변수 nOne에 저장한다.

이후 answer(초기 값은 n)에 1씩을 더하며 1 개수가 같아지는 시점에서 반복문을 중지하고 반환한다.

출처

알고리즘 연습 Level 3 | 프로그래머스