[PS] 다음 큰 숫자

문제

해결1

가장 무식한 방법은 n+1부터 1'000'000 까지 순회하면서 이진수로 변환했을 때 1의 개수가 같은지 체크해서 반환하는 방법이었고, 그거 제외하곤 마땅한 해법이 떠오르진 않았다.

근데 이게 정?답이었다. 생각해보니 1'000'000이면 이진수로 변환해봤자 2^19승 약 19자리이고, 최악의 케이스인 1부터 100만 까지 20자리를 순회한다고 하더라도 겨우 2000만이기 때문에 브루트포스로 해도 그렇게 오랜 시간이 소모되진 않는다.

소스코드1

#include <string>
#include <vector>

using namespace std;

int CountOne(int num)
{
    int ret = 0;
    while(num != 0)
    {
        if(num % 2 != 0) ret++;
        num /= 2;
    }
    return ret;
}

int solution(int n) {
    int answer = 0;
    int num = CountOne(n);
    for(int i=n+1; i<1'000'000;++i)
    {
        int tmp = CountOne(i);
        if(num == tmp)
        {
            answer = i;
            break;
        }
    }
    
    return answer;
}

굉장히 찝찝한 풀이고, 더 좋은 풀이가 없을까 하고 다른 사람의 풀이를 보자마자 매우 신기한 템플릿 클래스 하나를 봤다.

해결2

이 풀이는 bitset이라는 템플릿 클래스를 사용했는데,

https://en.cppreference.com/cpp/utility/bitset

template< std::size_t N >
class bitset;

간단하게 설명하면, 표준 논리 연산자(&, |, ^ 등등)로 조작 가능한 N 비트 고정 크기 시퀀스이다.
예를 들어 아래와 같이 사용할 수 있다.

bitset<8> bit1;    // 00000000
bitset<8> bit2(12) // 00001100

이 함수의 api 중에서 count라는 함수가 있는데, true(1)로 설정된 비트 개수를 반환해주는 치트키 기능이 있다.

즉, 원래 n의 1의 개수(이하 num)를 구하고, ++n의 bitset count값이 num과 같은지만 체크하면 된다.

소스코드2

#include <bitset>

using namespace std;

int solution(int n) {
    int num = bitset<20>(n).count();
    while(bitset<20>(++n).count() != num);
    return n;
}

매우 깔끔하게 코드가 나왔다.