Programmers - 2개 이하로 다른 비트

---

title: Programmers - 2개 이하로 다른 비트
date: 2022-06-23
tags:

• Algorithm

---

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

문제 요약

주어진 양의 정수 x보다 크지만 다른 비트가 2개 이하인 가장 작은 수를 vector에 집어넣은 후 return한다.

문제 풀이

비트 연산 문제이다. long long 범위이지만 10^15보다 작거나 같으며, 이는 최대 50비트만 확인하면 된다.
2개의 비트가 다르다는 것은 0을 1로 바꾸어 큰 수로 만들고, 그보다 작은 1 비트 중 가장 큰 위치의 비트를 0으로 만드면 된다는 의미이다.
다만, 0을 발견하면 바로 옆 비트는 1 혹은 0이 가장 작은 비트이다. 옆 비트가 0이라면 해당 비트에서 이미 발견하고 처리를 하였어야 한다.
고로 0을 발견하면 해당 비트를 더해주고, 아래의 비트만큼 빼주면 된다.



추가적으로, 다른 유저들의 풀이를 보던 중 감탄이 나오는 풀이를 발견하였다.
프로필을 조회할 수 없어서 입력하신 이름만 가져오는 것이 너무나도 죄송하다.
'김래영' 이라는 분이 작성한 프로그램은 아래와 같다.

'김래영' 님의 프로그램

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(ll& n : numbers) {
        ll idx = (~n & -~n);
        ll ans = n + idx - (idx >> 1);
        answer.push_back(ans);
    }
    return answer;
}

not 연산과 and 연산을 이용하면 처음으로 0이 나오는 가장 작은 비트를 발견할 수 있다.
이를 이용하여 비트를 탐색하는 과정 없이 바로 값을 구하여 집어넣을 수 있다.
이 정도의 사고를 할 수 있어야 비트 연산을 어느 정도 한다고 말할 수 있을 것 같다.

프로그램

#include <vector>

using std :: vector ;

vector < long long > solution ( vector < long long > numbers )
{
    vector < long long > answer ;
    long long * llpTemp = numbers.data () ;
    int iLen = numbers.size () ;



    for ( int i = 0 ; i < iLen ; ++i )
    {
        for ( int j = 0 ; j <= 50 ; ++j )                    // Max 50 bit, but it''s not all 1. So check only 50 bits
        {
            if ( 0 == ( ( llpTemp [ i ] >> j ) % 2 ) )        // Find 0
            {
                long long llTemp = 1LL << j ;

                answer.emplace_back ( llpTemp [ i ] + llTemp - ( llTemp >> 1 ) ) ;

                break ;
            }
        }
    }


    return answer ;
}