[프로그래머스 3단계] 알고리즘 32.다음 큰 숫자

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 32. 다음 큰 숫자

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

• N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다.
• 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다.

예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다.
N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요.

#include<iostream>

using namespace std;

int nextBigNumber(int n)

{

  int answer= 0;

  return answer;

}

int main()

{

  int n=78;

  //아래는 테스트 출력을 위한 코드입니다.

  cout<<nextBigNumber(n);

}

풀이 : 

이 문제의 핵심은 bit상의 1의 개수를 유지하면서 숫자를 올리는 것이다. 필자는 어떻게 쉽게 풀 수 있을까 고민하다가 무식한 방법을 쓰기로 했다. 나의 알고리즘은 다음과 같다.

1. 먼저 n의 bit 상의 1의 개수를 구한다.
2. n을 1씩 계속 증가시키면서 원래 bit상의 1의 개수와 현재 bit상의 1의 개수를 비교한다.
3. 만약 증가시킨 수와 원래 수의 bit상의 1의 개수가 같다면 그 수를 반환한다.

심플하고 무식하지 않은가 하하. 일단 입력 n에 대해서 bit 상의 1의 개수를 구하는 함수가 bit_count라고 할 때 나의 알고리즘을 코드로 나타내면 다음과 같다.

int nextBigNumber(int n)

{

int answer= n; //answer = n

int n_bit_count = bit_count(n); //n's bit count

do{

   answer += 1; //n + 1

}while(n_bit_count != bit_count(answer)); //n's bit count

  return answer;

}

이제 문제의 핵심중 하나인 bit상의 개수를 구하는 함수를 구해보자. 이 문제를 알기 위해선 프로그래밍의 모든 데이터는 bit로 이루어져 있고 bit 연산을 할 줄 알아야 한다. 일단 문제의 입력 78을 bit로 표현하면 1001110 이다. int는 32bit의 데이터이나 이를 생각하기 쉽게 8bit 단위로 표현해보겠다. 그럼 78은 01001110이다. 그렇다면 1의 개수를 구하기 위해선 어떻게 해야 할까? 나는 bit 연산 AND와 Left Shift 연산을 통해서 1의 개수를 구해보겠다. 다음을 살펴보자. 비교수를 i라고 해보자.

i = 00000001

n= 01001110

n & i = 00000000

왜냐하면 bit 연산 AND (&) 는 비교하는 두 bit가 모두 1이어야지 1을 결과로 내뱉기 때문이다. 이제 i 를 Left Shift 왼쪽으로 미뤄보자.

i <<= 1

i = 00000010

n= 01001110

n & i = 00000010

이 때는 같은 위치에서 1이 있음을 알 수 있다. C++ 은 조건식에서 수가 0이라면 false를 나머지는 true를 반환시킨다. 따라서, 8bit로 생각했을 때는 8번, int 형으로 생각했을때는 32번을 이렇게 왼쪽으로 밀면서 AND연산자를 이용하여 if (n & i) 는 조건을 만족킬 때 count를 올려주면 n의 bit 상 1의 개수를 알 수 있다. 코드는 다음과 같다.

int bit_count(int n)

{

int count = 0;

//bit 확인 bit가 1이면 count++

for (int i=0; i< sizeof(int) * 8; i++){

if (n & (0x01 << i) ){

count += 1;

}

}

return count;

}

 

여기서 sizeof(int) * 8 은 보통 시스템에서는 32번, int가 64 bit라면 64번 비교할 것이다. 이것은 시스템마다 다르기 때문에 일정하게 맞춰주기 위한 코드이므로 그냥 숫자 32를 써도 무방하다. 그리고 bit를 왼쪽으로 계속 미는 코드는 조건식에서 (0x01 << i) 이다. 그들을 반복문에 따라 나타내면 다음과 같다.

i=0 -> 0x0001(0...00000001) 

i=1 -> 0x0002(0...00000010) 

i=2 -> 0x0004(0...00000100) 

...

i=31->0x4000(0100...00000)

  

이렇게 수를 만들어줄 것이다. 문제의 조건 N(1≤N≤1,000,000)은 이 수들 안에 충분히 들어가므로 굳이 생각하지 않아도 된다. 이렇게 반복문을 돌면서 n에 대해 bit상의 각 자릿수에 대해 1의 개수를 세게 된다. 다음은 내가 짠 코드 전문이다.

int bit_count(int n)

{

int count = 0;

//bit 확인 bit가 1이면 count++

for (int i=0; i< sizeof(int) * 8; i++){

if (n & (0x01 << i) ){

count += 1;

}

}

return count;

}

int nextBigNumber(int n)

{

int answer= n; //answer = n

int n_bit_count = bit_count(n); //n's bit count

do{

   answer += 1; //n + 1

}while(n_bit_count != bit_count(answer)); //n's bit count

  return answer;

}

이제 3단계도 다 풀었다! 다음주부터는 4단계를 같이 풀어보도록 하자!