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

 

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 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

 

풀이

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(long long num : numbers){
        // 짝수의 경우 맨 마지막 숫자가 무조건 0이기 때문에 바로 다음수를 insert
        if(num%2==0){
            answer.push_back(num+1);
            continue;
        }
        
        long long bit = 1;
        while(true){
            bit *= 2;
            if((num&bit) == 0)
                break;
        }    
        bit/=2;
        answer.push_back(num + bit);
    }
    return answer;
}

 

1. 짝수의 경우 가장 오른쪽 비트가 0이기 때문에, 바로 다음 숫자가 f 값이 된다.

2. 홀수의 경우 오른쪽 비트가 무조건 1이 되며, 더했을 때의 올림을 생각해야 한다. 

    오른쪽부터 연속된 1비트의 개수가 n일 때, n-1 자리의 비트를 더한 값이 f가 된다. 

    10111의 f값 -> 11011 

    

 

 

---

다른 풀이

#include <vector>
std::vector<long long> solution(std::vector<long long> numbers) {
    std::vector<long long> answer;
    for (long long number : numbers) {
        long long bit = 1;
        while ((number & bit) > 0) bit <<= 1;
        answer.push_back(number + bit - (bit >> 1));
    }
    return answer;
}

 

비트 연산을 통해 홀수 짝수 나누지 않고 간단히 풀 수 있었다!

 

---

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

프로그래머스