LeetCode : 1073. Adding Two Negabinary Numbers

 

문제)

문제는 base - 2 (음의 기수 2진법)로 표현된 두 숫자 arr1과 arr2를 더한 결과를 구하는 것이다.

두 숫자는 배열 형식으로 주어지며, 배열의 요소는 0과 1로 구성되어 있다.

배열은 가장 최상위 비트(MSB)부터 가장 최하위 비트(LSB)까지 순서대로 정렬되어 있다.

            예를 들어, 배열 arr = [1, 1, 0, 1]은 - 2를 기반으로 하는 수로, 다음과 같이 계산된다 :
             (-2) ^ 3 + (-2) ^ 2 + (-2) ^ 0 = -3
            입력된 각 배열은 선행 0이 없으며, 따라서 배열은[0]이거나 배열의 첫 번째 요소는 1이다.

즉, 주어진 arr에서 2진법으로 계산한다. 이 때 -2로 계산.

두 값을 다시 이진법으로 표시해준 다음, 이를 벡터로 만들어서 리턴해주면 됨.

 

문제 난이도 : 중

 

 

소요시간 및 풀이)

 

class Solution 
{
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) 
    {
        vector<int> vec;

        int val1 = Sqr(arr1);
        int val2 = Sqr(arr2);
        int temp = 0;
        int i = 0;
        int sum = (val1 + val2);

        if (sum == 0)
            return { 0 };

        while (sum != 0) 
        {
            int remainder = abs(sum) % 2; // 절댓값의 나머지를 구함
            vec.insert(vec.begin(), remainder); // 나머지를 벡터의 첫 번째 위치에 삽입
            sum = (sum - remainder) / -2; // 나머지를 제외한 값을 다음 숫자로 업데이트
        }


        return vec;
    }

    int Sqr(vector<int> v)
    { 
        reverse(v.begin(), v.end());

        long long val = 0;
        
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i] == 0)
                continue;

            val += pow(-2, i);
        }

        return val;
    }
};

 

단순하게 정수 배열을 제곱해서 정수로 만들고, 그 정수를 다시 2진수로 변환하려 했다.

근데 정수형의 범위를 초과하는 case에서 실패한다.

내가 전에 실수했던 부분과 똑같았다.

 

 

소요 시간 : 못 풀고 정답 확인.

 

 

정답 코드

class Solution 
{
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) 
    {
        vector<int> vec;

        reverse(arr1.begin(), arr1.end());
        reverse(arr2.begin(), arr2.end());
        int len(max(arr1.size(), arr2.size()));
        int carry = 0;
        vector<int> ans;

        for (int i = 0; i < len + 2; i++)
        {
            //cur1과 cur2는 각각 arr1과 arr2의 현재 자릿수에 있는 값을 나타냄.
            //만약 현재 자릿수가 벡터의 크기를 벗어나면 벡터의 끝에 도달했다는 얘기이므로 0으로 초기화 해줌.
            int cur1 = i < arr1.size() ? arr1[i] : 0;
            int cur2 = i < arr2.size() ? arr2[i] : 0;

            int sum = cur1 + cur2 + carry; //현재 자릿수에서 두 수와 이전에 발생한 올림수(carry)를 더한 값.
            int r = sum % (-2); //sum을 -2로 나눈 나머지. -2진법에서는 나머지가 항상 -1또는 0이 된다.
            carry = sum / (-2); //sum을 -2로 나눈 몫을 나타냄. 이것이 다음 자릿수에 대한 올림수가 된다.

            //만약 r이 음수라면 올림수를 추가하고 r이 0또는1이 되도록 한다.
            if (r < 0)
            {
                carry++;
                r += abs(-2);
            }
            ans.push_back(r);
        }

        while (ans.size() > 1 && ans.back() == 0)
        {
            ans.pop_back();
        }

        reverse(ans.begin(), ans.end());

        return ans;
    }
};