Coding Test] 2개 이하로 다른 비트

[Programmers School 문제 링크]

• Code

#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <math.h>

using namespace std;

#define BITSIZE 50
string F(long long n)
{
    string s = bitset<BITSIZE>(n).to_string();
    s.erase(s.begin(), s.begin() + s.find('1'));
    reverse(s.begin(), s.end());
    return s;
}

int Count(string s)
{
    int n = s.find('0');
    return n > 0 ? n + 1 : s.size() + 1;
}

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    //1
    for(int i = 0; i < numbers.size(); i++)
    {
        //2-1
        if(numbers[i] % 2 == 0)
            answer.push_back(numbers[i] + 1);
        //2-2
        else
        {
            //a)
            int size = Count(F(numbers[i])) - 2;
            //b)
            long long value = 1;            
            for(int j = 0; j < size; j++)
                value += pow(2, j);
            //c)
            answer.push_back(numbers[i] + value);
        }
    }
    return answer;
}

• 알고리즘 설명

1. numbers 순회

2-1. numbers[i]가 짝수면 numbers[i]에 1을 더한 값을 저장

2-2. numbers[i]가 홀수면

a) 현재 숫자+1의 비트 상으로 2^0 자리부터 처음 나오는 '1'의 위치 + 1(현재 숫자보다 큰 숫자들의 다른 비트의 갯 수)을 구하고, 1~2개가 다르면 되므로 - 2

b) 무조건 기존 수보다 크기 때문에, value += 1 + 2^0 + 2^1 ... 2^size-1

c) numbers[i]에 value를 더한 값을 저장

• 동작 예시

1. numbers = { 2, 7 }

2-1. numbers[0] = 2, 짝수이므로 answer.push_back(numbers[0] + 1);

2-2. numbers[1] = 7, 홀수이므로

a)

111 (7)

0001 (8)

size = 3 + 1 - 2

+3 = 비트(8)의 2^0에서부터 처음 나오는 1의 인덱스 위치(s.find(s.begin(), s.end(), '0')

+1 = 인덱스는 0부터인걸 보조하기 위한 +1

-2 = 1~2개 다르면 조건 충족

size = 2

b)

int value = 1; (+1은 기본으로 들어감)

for(int i = 0; i < size; i++)

value += 2^i; //1, 2, 4, 8, ..., 2^n

c)

answer.push_back(numbers[i] + value);

• 함수 기능 설명

//long long 타입의 수의 Bit(string 타입)화

#define BITSIZE 50    //비트 갯수
string F(long long n)
{
    //50개의 비트로 변환 후 string에 저장. ex) 0000000...001101 (13)
    string s = bitset<BITSIZE>(n).to_string();
    //불필요한 0들 제거. ex) 제거 후 = 1101
    s.erase(s.begin(), s.begin() + s.find('1'));
    //string의 인덱스와 비트의 순서를 맞추기 위해 반전. ex) 반전 후 = 1011
    reverse(s.begin(), s.end());
    return s;
}

/*
    s[0]부터 처음 나오는 '0'을 탐색, +1을 했을때 1이 되는 위치.
    +1 이후 달라지는 비트 수는 찾아낸 위치(인덱스)+1
    '0'을 찾지 못한 경우(111)엔  size+1을 반환
*/

int Count(string s)
{
    int n = s.find('0');
    return n > 0 ? n + 1 : s.size() + 1;
}

• 추가 설명

2-2의 알고리즘으로 2-1의 경우도 동작할 수 있어 굳이 if else문으로 상황을 나누지 않아도 되지만 짝수인 경우를 별도로 둔 것은 실행 시간 단축을 위해서이다.

짝수의 첫 자리(2^0)은 항상 0이므로 +1한 값이 정답이다. 하지만 이를 2-2처럼 동작하면 숫자의 비트 변환, string의 불필요한 부분 제거 및 반전 등 불필요한 계산을 하여 실행시간에 영향이 가기 떄문에 별도의 조건을 사용했다.