프로그래머스 월간 코드 챌린지 시즌2 2개 이하로 다른 비트 c++(구현)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

문제 설명

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

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

예를 들어,

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

 

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

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

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

---

입출력 예

 

 

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

풀이

처음 접해보는 비트 문제이다.

수가 짝수일 때의 규칙은 찾았는데, 맨 우측이 아닌 중간이나 왼쪽에 있는 비트를 어떻게 바꿀지를 고민하다가

못 푼 문제이다.

 

우선 짝수일 때의 규칙은

2 == 0010

4 == 0100

6 == 0110

8 == 1000

으로 항상 최하위 비트가 0이다. 

이 경우에는 1만 더해주면 'x보다 크고 비트와 1~2개 다른 수들 중에서 제일 작은 수'라는 조건을 만족한다.

 

그럼 나머지 경우인 홀수일 때는

5 == 0101

7 == 0111

11 == 1011

으로 항상 최하위 비트가 1인 경우인데,

이 경우는 우선 하나씩 수를 늘려가면서 조건을 맞춰봤다.

5(0101) -> 6(0110)

7(0111) -> 11(1011)

11(1011) -> 13(1101)

우선 조건에서 답은 x보다 항상 커야하기 때문에 비트0을 1로 바꿔줘야하는 과정이 필수적이다.

그런데 제일 작은 수를 찾아야 하기 때문에 왼쪽보다 오른쪽에 있는 비트0을 1로 바꾸는 것이

수가 조금 커질 것이다.

이 규칙대로 7을 바꿔보면 7(0111) -> 15(1111)가 된다.

현재 비트는 1개가 다르고, x보다 커야한다는 조건을 만족한다.

하지만 나머지 조건을 보면 우리가 찾아야 하는 답은 이중에 가장 작아야 하고, 우리는 1개의 비트를 더 바꿀 수 있다.

그러면 나머지 1개의 비트를 어떻게 바꿔야 수가 작아질까?

그렇다 이번엔 7(0111)에서 가장 왼쪽에 있는 비트1을 0으로 바꿔주면 수가 많이 작아질 것이다.

이 규칙까지 적용해서 7을 바꿔보면 7(0111) -> 11(1011)으로 조건을 만족하는 가장 작은 수가 된다.

 

홀수일 때의 요지는 비트가0인 가장 최하위 비트를 1로 바꾸고,

비트가 1인 가장 최상위 비트를 0으로 바꾸면 되는 것이다.

 

 

이제 이 규칙을 코드로 구현해보자.

 

최하위 비트를 구하는 법을 알고 있지 않더라도, 이렇게 저렇게 머리를 굴려 비트 부호를 써보면 구현을 할 수 있었을 것이다. 다만 시간이 중요한 코딩 테스트에서는 마음이 급해 쉽게 생각할 수 없을 것이다..

 

비트가 1인 가장 최상위 비트는 비트가 0인 최하위 비트의 바로 오른쪽에 있으므로.

우리는 비트가 0인 가장 최하위 비트를 구해줄 것이다.

&연산자를 쓰면 두 비트가 모두 1이어야 1이 나오기 때문에 이를 이용하면 구할 수 있을 것 같다.

 

우선 비트가 0이면 &연산을 아무리 해도 0밖에 나오지 않으므로 비트가 0인 최하위 비트를 1로 만들어줄 것이다.

num ==9일 때 

1001에서 최하위 비트인 0을 1로 바꾸려면 1을 더하면 된다.

그러면 10(1010)이 되고 10(1010)의 보수를 구하는 -연산을 하면

0110이 된다.

이 0110과 10(1010)을 &연산 하면 0010로 즉 비트가 0인 최하위 비트를 알 수 있다.

이 0010을 lastbit이라고 하면 이를 이용해서

비트가 0인 최하위 비트는 1로 바꿔주고 // num | lastbit == 1011

비트가 1인 최상위 비트는 0으로 바꿔준다 // (num | lastbit) &(~(lastbit>>1))  

 

최하위 비트를 구하는 게 어렵지, 시간복잡도는 O(n)이고 코드 또한 간단하다.

코드

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(int i=0; i<numbers.size();i++){
        if(numbers[i]%2==0){
            answer.push_back(numbers[i]+1);
        }
        else{
           long long lastbit = (numbers[i]+1) & -(numbers[i]+1);
            answer.push_back((numbers[i]|lastbit) & (~(lastbit>>1)));
        }
    }
    return answer;
}