[Lesson1/C++] Codility - BinaryGap

코딜리티로 시험 준비해야 할 일이 있어서 lesson에 있는 문제를 살짝 풀어보다가

다른 코딩테스트 대비 플랫폼보다 히든케이스를 생각하는 부분이나,

시간 복잡도를 확인하는데 더 도움이 될 것 같아서 계속해서 풀어가고 있다!

 

lesson1은 Iterations을 주제로 가지고 있고, Easy 난이도의 문제가 하나 있다.

---

0. 문제

 

간단하게 요약하자면, 1로 시작하고, 1로 닫히는 비트 중에서,

1과 1사이에 있는 0의 개수가 가장 많을 때 그 개수를 출력하는 문제이다.

만약에 그런 경우가 없다면 0을 출력해야한다.

---

1. 문제풀이 및 코드

먼저 10진수로 주어지는 숫자를 이진수로 만들 필요가 있었다.

그리고 어차피 이진수가 0과 1이므로 그 이진수는 bool타입의 vector에 저장했다. 

그리고 여기서 reverse를 한 이유는 아래와 같이 이진수를 구하다보면, 가장 상위 비트가 아래로 내려가있기 때문이었다.

 

그리고 1로 시작하는지 안하는지를 start1이라는 플래그로 점검했다.

start1이 이미 true인 상태에서, binary[i]가 또 1이라면,

0의 개수를 세고 있던 cnt를 이용해서 answer를 업데이트하고,cnt를 초기화한다.

 

ex. 100010001을 예로 들자면, 중간에 빨간색 1을 마주치면,

다시 뒤에서 0 카운트를 시작해야하므로, 다시 cnt를 0으로 바꾸는 것이다.

 

#include <bits/stdc++.h>
//returns the length of its longest binary gap, 없다면 0출력
//이진수로 바꿔서, 1과1사이에 있는0의 개수를 세고, 최대 0의 개수를 출력하기
int solution(int N) {
    int answer = 0;
    vector<bool> binary;
    while(N>0){
        binary.push_back(N%2);
        N=N/2;
    }
    reverse(binary.begin(),binary.end());
    
    bool start1 = false;
    int cnt = 0;
    for (int i=0;i<(int)binary.size();++i){
        if (start1==false && binary[i]==1) start1=true;
        else{
            if (start1 && binary[i]==0) {
                cnt ++;
            }

            if (start1 && binary[i]==1){
                answer = max(answer,cnt);
                cnt=0; 
            }   
        }
    }
    return answer;
}