[ 프로그래머스 lv 2 ] 2개 이하로 다른 비트 (c++)

 

 

문제

---

 

 

 

풀이

---

 

처음에 생각한 풀이방법은 xor 비트 연산을 이용하는 것이었다. 문제 예시로 7과 8 사이의 다른 비트 개수를 셀 때 xor를 사용하면 4개라는 사실을 쉽게 알 수 있었기에 그런 생각이 들었다.

 

문제는 xor을 이용해서 numbers[i]보다 큰 수들을 차례로 찾아가니 시간 초과가 발생했다. 문제에서 numbers의 최대 원소 크기는 10의 15승으로, 반복문을 30번 정도로 설정해도 한 번 xor 비트 연산 시 꽤 많이 비교하는 작업이 발생했다.

 

 

이 때문에 numbers의 길이 100000   x   반복문 대략 50번 (bit를 1씩 왼쪽 쉬프트 연산하며 1 개수를 셈)   x  내부에서 비트 연산 횟수 (xor 연산하는데 걸리는 시간) 을 계산하면  1억을 넘어가게 되었다...

 

 

 

그래서 다른 방법을 찾아보니, 규칙을 찾아서 구현해야했다. 일단 기억해야할 요소들을 정리하면 이렇다.

 

 

1. 주어진 수 보다 크면서, 가장 작은 수. 즉 가장 가까운 수라고 생각하면 이해가 쉽다. 

 

2. 크면서 동시에 주어진 수와 비트가 1개 내지 2개가 달라야한다. 

 

 

 

예시에서 f(2)는 3이 나오는 데, 이는 2의 이진수 10 보다 비트가 1개다르면서 가장 가까운 수가 3이기 때문이다. 여기서 규칙을 하나 찾을 수 있는데, 

 

짝수는 무조건 이진수로 변환하면 마지막이 0으로 끝나기 때문에, 마지막 자리 0을 1로 증가시키면 f(x)값을 구할 수 있게 된다.

 

 

이는 1번 규칙 가장 가까운 수에 부합하며( 짝수를 이진수로 변환한 수의 마지막 자리 0을 1로 바꾸는 건 즉 그 수에서 1 증가시킨다는 것으로, 이보다 가까운 수는 존재할 수 없다.) , 동시에 2번 규칙 중 비트가 1개 달라야한다 에 부합하기 때문에 가능하다. 

 

 

 

 

문제는 홀수다. 홀수의 f(x)를 구할 때는 좀 더 생각해야 했다.

 

일단 2번 규칙에 부합하기 위해서는 비트가 달라져야 한다. 0이 1이 되거나, 1이 0이 되어야 한다. 그런데 1이 0으로 되는 것은 숫자가 작아지는 것이니, 1번 규칙을 지키기 위해 우선적으로 고려할 것은 0을 1로 만드는 것이다. 

 

예로 7의 이진수 0111을 보면, 1번 규칙에 부합하기 위해서 0을 1로 바꾼수를 찾아보면 이렇다.

 

0000 0111   --    7

0000 1111   --    15

 

0001 0111

...

 

 

물론 10111도 7보다 크지만 이러면 가장 가까운 수가 절대 되지 않을 것이다. 즉, 일단 가장 가까운 수로 만들기 위해 0을 1로 바꾸는 작업을 할 때는, 가장 작은 자리수의 0을 찾아 바꿔야 한다.

 

 

하지만 이렇게 찾은 15는 정답이 아니다. 2번 규칙에서 우리는 비트를 두 개 까지 바꿀 수 있다. 15에서 비트를 하나 더 바꿔서 7보단 크지만 그래도 15보단 작은 수로 바꿀 수 있을까?

 

 

0000 1111 -- 15

 

0000 1011  --  11

 

0000 1101  -- 13

 

0000  1110  -- 14

 

 

비트 하나를 1에서 0으로 변경하면 크기가 작아진다고 했다. 15의 비트 하나씩 0으로 바꿔보니, 11이 가장 작으면서 조건에 부합한다. 여기서 알 수 있는건,

 

 

1. 가장 낮은 자리의 0을 1로 변경

 

2. 그 자리의 뒷자리를 0으로 변경

 

 

이러면 이 문제에서 요구하는 정답을 찾게되는 것이다. 

 

왜 그런가? 만약 1로 변경한 자리의 뒷자리가 아니라 앞자리를 0으로 바꾼다면 오히려 수가 기존의 숫자보다 더 작아질 것이다. 그리고 바로 뒷자리가 아니라 더 뒤의 비트를 0으로 바꾼다면, 11이 아니라 13, 14처럼 7보단 크지만 더 작은 수가 존재하는 상태가 되기 때문이다.

 

 

비트에 있어 자리의 무게에 대해서 다시 생각해보는 계기가 되었다.

 

 

 

코드 

---

#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 b = 1;
            while (true) {
                if ((numbers[i] & b) == 0) break;
                b *= 2;
            }
         
            answer.push_back(numbers[i] + (b / 2));
        }
    }
    return answer;
}

 

 

코드를 해석해 보자면, numbers[i]가 짝수일 때는 1을 더한 값이 정답이니 그대로 push하고, 홀수이면 위에서 말한 규칙을 적용해서 정답을 구한다. 

 

 

numbers[i] & b에서 의미하는 것은 and연산으로, 그 자리가 1인지 알아보는 것이다. 0000 1111과 0000 0001 을 and연산하면 1이 나오는데, 이걸로 첫 번째 자릿수가 1인 걸 알 수 있다. 그 뒤 b에 2를 곱해서 자리를 왼쪽으로 옮기는 것이다. 

 

 

 

 

중요한 점은 numbers[i] & b를 할 때 괄호를 씌워주는 것이다. 연산자 우선순위가 있어 괄호가 없으면 == 부터 실행이 되어서 틀리게 된다.