[프로그래머스] 다음 큰 숫자

내 접근법:

완전 탐색방식

현재 숫자의 1의 갯수를 셉니다
매번 현재 숫자의 1의 갯수와 비교대상의 숫자 개수를 셉니다
1의 갯수가 같다면 비교대상이 더큰지 확인하고 반환합니다.

#include <string>
#include <vector>

using namespace std;

int numberToBinaryOne(int n)
{
    int res = 0;
    while(n > 0)
    {
        if(n % 2 == 1) res++;
        n /= 2;
    }
    return res;
}

int solution(int n) {
    int answer = 0;
    int temp = n + 1;
    while(1)
    {
        if(numberToBinaryOne(n) == numberToBinaryOne(temp) && temp > n)
            return temp;
        else 
            temp++;
    }
    return answer;
}

다른 풀이법: Bitset 활용하기

bitset 헤더를 사용하여 2진수 변환과 1의 개수를 bitset의 count 함수를 이용하여 셉니다.

#include <string>
#include <vector>
#include <bitset> // 헤더 추가

using namespace std;

int solution(int n) {
    // n의 1의 개수를 미리 구함
    int num = bitset<20>(n).count();

    while (1) {
        n++;
        // 증가시킨 n의 1의 개수가 num과 같으면 리턴
        if (bitset<20>(n).count() == num) return n;
    }
}

다른 풀이법: 비트 조작 활용

숫자의 가장 오른쪽 1뭉치를 찾아 왼쪽으로 이동 시키고, 나머지 1들을 오른쪽 끝으로 정렬합니다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int smallest, ripple, ones;

    // 1. 가장 오른쪽의 1을 찾음 (smallest)
    smallest = n & -n;

    // 2. 가장 오른쪽 1과 그 왼쪽의 비트들을 더해 패턴을 만듦 (ripple)
    ripple = n + smallest;

    // 3. 원래 숫자와 XOR 후 shift 하여 나머지 1의 개수를 맞춤 (ones)
    ones = n ^ ripple;
    ones = (ones) / smallest >> 2;

    // 4. 최종 결과 결합
    return ripple | ones;
}

숫자의 표현[프로그래머스]

짝지어 제거하기[프로그래머스]