LV2.2개 이하로 다른 비트

https://school.programmers.co.kr/learn/courses/30/lessons/77885

프로그래머스

---

첫번째 접근 방법 :  비트연산(XOR) 접근

비트 연산 문제로 파악하여 비트를 쉽게 파악하기 위해 bitset을 사용
2개 이하 다른 비트를 찾기 위해 XOR 비트연산을 이용하여 [1의 갯수 < 2]의 조건을 찾아 정답을 찾음
하지만 인자값으로 큰 숫자가 들어올 경우 XOR을 해야되는 연산 수가 늘어나며 시간 복잡도에서 문제가 발생

---

두번째 접근 방법 : 각 비트의 규칙을 찾음

2진 숫자(numbers)	2진 변환(answer)	처음보는 0 뒤의 1숫자 index	numbers에 더해주는 값
010(2)	011(3)	0(처음 보는 0 뒤에 1이 없음)	+2^0
011(3)	101(5)	1(0의 index는 두번째,2-1 =1)	+2^1
100(4)	101(5)	0(처음 보는 0 뒤에 1이 없음)	+2^0
101(5)	110(6)	0(0의 index는 첫번째, 1-1=0)	+2^0
110(6)	111(7)	0(처음 보는 0 뒤에 1이 없음)	+2^0
111(7)	1011(11)	2(0의 index는 세번째 3-1=2)	+2^2

규칙을 보면 numbers의 비트들에서 오른쪽에서 처음으로 보는 0 뒤의 1숫자의 index를 2제곱해준 값을
numbers에 더해주면된다. 그렇게하면 비트는 무조건 2이하로 바뀌게 되는 조건을 만족한다.

 

ex)1 010(2)의 [처음보는 0뒤에 1 index]는 0이고, 그 값을 2^n에 대입하면

010 + 2^0 = 011(3) 값이 나온다.

ex2)011(3)의  [처음보는 0뒤에 1 index]는 1이고, 그 값을 2^n에 대입하면

011 + 2^1 = 101(5)  값이 나온다.

---

코드영역

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(long long i =0; i < numbers.size() ; i++)
    {
        long long number = numbers[i];
        long long index_0 = 0; //처음보는 0의 index
        
        //number를 이진법으로 변환하며 처음 만나는 0 찾기
        while(number > 0)
        {
            if(number % 2 == 0) { break; } // 해당 이진법의 자리가 0인경우 탈출
            index_0++; //0이 아닌경우 index가 증가함
            number *= 0.5;
        }

        //0뒤의 숫자1의 index를 알아야하기 때문에 -1을 계산
        if(index_0 > 0) { index_0 -= 1;} 

        //number에 더해줄 2^count 를 구함
        long long sum = 1;
        for(long long i =0; i< index_0; i++) {  sum *= 2;}
        
        answer.push_back(numbers[i] + sum);
    }
    return answer;
}