[C++ ] 완전 탐색 (Brute-force Search) | 프로그래머스 2단계 다음 큰 숫자 문제 풀이 | Bitset 이진수 변환

문제 설명

프로그래머스

 

해결 코드

#include <string>
#include <vector>
#include <bitset>
using namespace std;

int solution(int n) {
    int answer = 0;

    bitset<32> bit1 = bitset<32>(n);        // n을 2진수로 변환
    string N = bit1.to_string();            // 문자 탐색의 용이성을 위해 이진수를 string으로 형변환
    int N_count = 0;                        //n의 이진수에서 1의 개수
    
    for(int i =0; i<32; i++){               //n의 2진수에서 1의 개수 구하기
        if(N[i]=='1') N_count++;
    }
    
        
    int k = n + 1;                          //k는 n+1부터 시작해서 완전 탐색
    while(1){
        bitset<32> bit2 = bitset<32>(k);
        string K = bit2.to_string();
        int K_count = 0;
        for(int i =0; i<32; i++){           //k의 2진수에서 1의 개수 구하기
            if(K[i]== '1') K_count++;
        }
        if(N_count==K_count) {              //n 이진수와 1의 개수 똑같은 k 값 찾으면 while문 탈출
            answer = k;
            break;
        }
        k++;                               
    }    
    
    return answer;
}

오늘 배운 것은 C++에서 이진수 변환을 쉽게 해주는 Bitset이다. 

비트셋 선언은 아래와 같다.

bitset<데이터 비트수>(변환할 십진수 );

예를 들어 정수 8의 이진수를 구하고 싶다면, ' bitset<32>(8) ' 이렇게 해주면 된다.

여기서 '<>' 안에 들어가는 비트수는 '()'에 들어가는 수의 데이터 타입에 따라 비트 수를 넣어주면 된다.

int면 32, char면 8, double이면 64 이렇게.

 

이렇게 변환한 이진수에서 1의 개수를 찾아야 하는데, 나는 문자 하나하나 탐색에 용이한 string을 사용하기 위해서

bitset을 string으로 형변환 해주었다. bitset STL에 bitset을 string으로 자동 형변환해 주는 메서드 'to_string()'이 존재해서 손쉽게 변환할 수 있었다. 

 

Bitset에 대한 자세한 설명은 아래 포스트를 참고하자

비트셋(Bitset) STL 사용 방법

 

나는 완전 탐색을 이용해서 k를 찾아냈는데, k는 n보다 큰 수이므로 n+1부터 시작해서 

k를 이진수로 변환하고 n과 같은 방법으로 1의 개수를 찾아낸 뒤, 

n의 이진수에서 1의 개수인 N_count와 k의 이진수에서 1의 개수인 K_count가 같으면 탐색 중단,

그렇지 않으면 k++ 해서 다시 while문 코드를 실행하는 방식으로 반복문을 구성해 완전 탐색을 구현했다.