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

 1트)

N보다 큰 수랑 비슷하게

++해가면서

1의 개수가 1~2개 차이나는 애 찾아내기!

#include <string>
#include <vector>
#include <iostream>
#include <bitset>
using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;

    for(auto x : numbers){
        bitset<50>num = x;
        
        while(1){
            int dif = 0;
            x++;
            bitset<50>n = x;
            for(int i =0; i<50; ++i){
                if(n[i] != num[i]){
                    dif++;
                }
                if(dif == 3) break;
            }
            if(dif <= 2){
                answer.push_back(x); break;
            }
        }
    }
    
    return answer;
}

틀리고나서 생각해보니까

틀리는게 너무나 당연한게

현재 코드는 x를 1씩 증가시키며 매번 50비트 전체를 비교 → 최악의 경우 O(N × K × 50) (K = numbers 크기)니까

입력이 커지면 시간초과가 날 수밖에 없음....

 

근데 고민해보니까 규칙이 있는게

하나 큰거를 해야하니까

짝수는 무조건 맨 마지막 1자리가 0 일거니까 이거만 1로 바꿔주면

비트가 1개만 다른 바로 다음 큰 수를 찾을 수 있고,

홀수는 제일 뒤에 있는 0을 1로 바꾸고

그 앞의 1을 0으로 바꾸면 비트가 2개만 다른 큰 수를 찾을 수 있음!

 

#include <string>
#include <vector>
#include <iostream>
#include <bitset>
using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;

    for(auto x : numbers){
        bitset<50>num = x;
        int zero_loca;
        for(int i =0; i<50; ++i){
            if(!num[i]){
                zero_loca = i;
                num[i] = 1;
                break;
            }
        }
        zero_loca--;
        while(zero_loca>=0){
            if(num[zero_loca]){
                num[zero_loca] = 0;
                break;
            }
            zero_loca--;
        }
        auto n = num.to_ullong();
        answer.push_back(n);
    }
    return answer;
}

 

이걸 근데 조금 더 간단하게 풀 수 있는 방법이 있나

// 다른 사람 풀이 참고 1
#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;
}


// 다른 사람 풀이 참고 2
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(ll& n : numbers) {
        ll idx = (~n & -~n);
        ll ans = n + idx - (idx >> 1);
        answer.push_back(ans);
    }
    return answer;
}