BinaryGap

난이도 : Easy

번역 : 문제 양의 정수 N 내의 이진 간격은 N의 이진 표현에서 양쪽 끝에서 1로 둘러싸인 연속 0의 최대 시퀀스입니다. 예를 들어, 숫자 9는 이진 표현 1001을 갖고 길이가 2인 이진 간격을 포함합니다.
숫자 529는 이진 표현이 1000010001이고 두 개의 이진 간격(길이 4 중 하나와 길이 3 중 하나)을 포함합니다.
숫자 20에는 이진 표현 10100이 있고 다음을 포함합니다.
길이가 1인 하나의 이진 간격. 숫자 15는 이진 표현 1111을 가지며 이진 간격이 없습니다.
숫자 32는 이진수 표현이 100000이고 이진수 간격이 없습니다.
함수 작성: int 솔루션(int N); 양의 정수 N이 주어지면 가장 긴 이진 간격의 길이를 반환합니다.
N에 이진 간격이 포함되지 않은 경우 함수는 0을 반환해야 합니다.
예를 들어, N = 1041이 주어지면 함수는 5를 반환해야 합니다.
N은 이진 표현이 10000010001이고 가장 긴 이진 간격의 길이는 5이기 때문입니다.
N = 32가 주어지면 함수는 0을 반환해야 합니다.
N은 이진 표현이 '100000'이고 따라서 바이너리 갭이 없습니다.
다음 가정에 대한 효율적인 알고리즘을 작성하십시오.
N은 [1..2,147,483,647] 범위의 정수입니다.

 

문제의 이해

이진수의 1과 1 사이에 0이 있는데 0의 갯수가 많은 것의 수를 return 하라.

 

문제 해결 아이디어

최초 '1'의 위치를 찾아야 하지만 '11'의 경우도 있기에 '10' 시작하는 숫자 위치를 찾고 다음 1의 위치를 찾아 position 값을 이용해서 0의 갯수를 세고 이 것의 반복하여 가장 큰 0의 갯수를 구한다.

 

필요한 로직 구상

1. 입력된 숫자를 이진으로 변환

2. 원하는 스트링 찾기

 

 

내가 푼 답

#include <bitset>

int solution(int N) {
    // write your code in C++14 (g++ 6.2.0)
    //cout << N << endl;
    bitset<32> foo (N); // 1)
    //cout << foo << endl;

    int counts_one = foo.count();
    int zero_count = 0;
    if(counts_one < 2) {
        return 0;
    }
    string str = foo.to_string<char,std::string::traits_type,std::string::allocator_type>(); //2)
    size_t nPos = str.find("10");
    //cout << "10 nPos = " << nPos << endl;

    size_t nnPos ;
    while(nPos != string::npos){

        nnPos = str.find("1", nPos+1);
        if(nnPos == string::npos || nnPos == 1)
            return zero_count;
        //cout << "zero_count = " << zero_count << " nnpos = " << nnPos << endl;            
        zero_count = max(static_cast<int>(nnPos - nPos - 1),zero_count); //3)
        nPos =  nnPos;
    }
    //cout << "result : zero_count = " << zero_count << endl;               
    return zero_count;
}

 

코드 설명

1) bitset<32> foo (N);

bitset 은 < > 사이에 들어간 수 만큼 이진수로 변형을 하는데 아래 조건이 있어서 해당 수를 모두 포함하는 32로 하였고 입력된 자연수 N 을 이진수로 변형한다.

N은 [1..2,147,483,647] 범위의 정수입니다.

2) string str = foo.to_string<char,std::string::traits_type,std::string::allocator_type>();

이렇게 변형한 이진수를 서칭하기 위해 str 으로 변형을 한다. bitset 에 string 변환은 위와 같이 처리를 해줘야 한다.

 

3) max(static_cast<int>(nnPos - nPos - 1), zero_count);

str 에서 찾은 포지션은 size_t 형 으로 return 을 한다. min, max 함수의 param 값이 template 이라 비교할 param1, 2의 값이 같은 형이면 되는데 그냥 size_t 로 변경해주면되는데 저는 굳이 size_t 를 int로 변환해서 썼네요 ^^; 

L typedef unsigned int size_t;

template<class T>
const T& max (const T& a, const T& b)

 

혹시나 설명이 부족한게 있으시면 언제든지 문의 부탁 드립니다.