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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

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의 모든 수 ≤ 10^15

 

풀이

입출력 예시

 

풀이

numbers안에 있는 모든 수가 최대 10^15 이라고 하니까, 비트 크기를 50으로 잡아주자. 비트가 다른 것을 아는 방법은 XOR연산을 이용한다. XOR 연산의 결과는 비트가 다를 때 1이니까 말이다.

#include <string>
#include <vector>
#include <bitset>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for (const auto& number : numbers) {
        bitset<50> bit1(number);
        bitset<50> tmp(7);
        
        long long num = number + 1;
        while (tmp.count() > 2) {
            bitset<50> bit2(num);
            tmp = bit1 ^ bit2;
            num++;
        }
        answer.push_back(--num);
    }
    
    return answer;
}

---

그런데 다시 보니까 numbers의 길이가 최대 10만에 number의 크기가 최대 1,000,000,000,000,000이다. 이거... 시간 초과가 날 것이 분명하다.

정말이다. 아마 문제의 의도는 비트로 변환해서 직접 연산하는 방법이 아닌 것 같다. 그럼 어떤 방법이 있을까. 규칙을 찾아보자.

0 = 0, 1 = 1
1 = 01, 2 = 10
2 = 10, 3 = 11
3 = 011, 5 = 101
12 = 1100, 13 = 1101
19 = 10011, 21 = 10101
100 = 1100100, 101 = 1100101
163 = 10100011, 165 = 10100101

 

짝수일 땐 항상 +1인 수들이 비트가 2개 이하로 다르면서 가장 작은 수였다. 홀수일 경우에는 조금 생각이 필요했는데, 규칙을 생각해본 결과 다음과 같았다.

 

1. 최하위 비트에서 상위 비트로 이동하면서 0인 부분을 찾는다.
2. 찾으면 그 부분을 1로 하고 바로 아래 비트를 0으로 바꿔주면 된다.

 

#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 tmp = number - 1;
            while(tmp <= number) {
                tmp = number ^ num;
                if (tmp < number) { // 해당 비트가 1이었다면 연산 결과 수가 더 줄어든다.
                    tmp ^= num;     // 수를 되돌려주고
                    num *= 2;       // 상위 비트로 간다.
                }
                else {
                    tmp ^= num / 2; // 해당 비트의 하위 비트를 바꿔준다.
                }
            }
            answer.push_back(tmp);
        }
    }
    
    return answer;
}