[프로그래머스] 2개 이하로 다른 비트

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

프로그래머스

문제 유형 : 비트마스킹

문제 난이도 : Level 2

 

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수비트다른 비트의 개수

2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수비트다른 비트의 개수

7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

 

풀이

수가 짝수인 경우에, 1만 더해주면 가장 작은 비트가 1~2개 다른 수이다.

수가 홀수인 경우, 상위 비트로 옮기면서의 나오는0을 1로 바꾸고, 그 아래 자릿수를 0으로 바꾼다.

코드

C++

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for (const auto& number : numbers) {
        if (number % 2 == 0) {
            answer.push_back(number + 1);
        }
        else {
            long long num = 2;
            long long x = number - 1;
            while(x <= number) {
                x = number ^ num;
                if (x < number) {
                    x ^= num;  
                    num *= 2;    
                }
                else {
                    x ^= num / 2;
                }
            }
            answer.push_back(x);
        }
    }
    
    return answer;
}