[LeetCode - C] 67. Add Binary

Add Binary - LeetCode

Given two binary strings a and b, return their sum as a binary string.

 

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

 

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

---

Solution 1

(Wrong Solution)

 

숫자로 바꿔 합산한 뒤

 

다시 이진법 적용했다.

 

int라 처리할 수 있는 값이 매우 한정적이다.

char *addBinary(char *a, char *b)
{
    int     a_i;
    int     b_i;
    int     sum;
    int     mul;
    int     size;
    int     r_i;
    char    *ret;
    
    a_i = 0;
    b_i = 0;
    sum = 0;
    mul = 1;
    size = 1;
    while (a[a_i])
        a_i++;
    while (b[b_i])
        b_i++;
    a_i--;
    b_i--;
    while (a_i != -1 || b_i != -1)
    {
        if (a_i != -1)
        {
            sum += (a[a_i] - '0') * mul;
            a_i--;
        }
        if (b_i != -1)
        {
            sum += (b[b_i] - '0') * mul;
            b_i--;
        }
        mul *= 2;
        size++;
    }
    if (sum >= mul)
    {
        ret = (char *)malloc(sizeof(char) * (size + 1));
        r_i = size;
    }
    else
    {
        ret = (char *)malloc(sizeof(char) * size);
        r_i = size - 1;
    }
    ret[r_i--] = '\0';
    if (!sum)
    {
        ret[0] = '0';
        return (ret);
    }
    while (sum)
    {
        if (sum % 2)
            ret[r_i] = '1';
        else
            ret[r_i] = '0';
        r_i--;
        sum /= 2;
    }
    return (ret);
}

---

Solution 2

 

노가다해서 풀었다.

 

노가다했기 때문에 따로 설명할 게 없다.

 

malloc size땜에 개노답이다 정말..

#include <stdlib.h>

char *addBinary(char *a, char *b)
{
    int     a_i;
    int     b_i;
    int     size;
    int     carry;
    char    *ret;
    
    a_i = 0;
    b_i = 0;
    carry = 0;
    while (a[a_i + 1])
        a_i++;
    while (b[b_i + 1])
        b_i++;
    size = a_i > b_i ? a_i : b_i;
    while (a_i != -1 && b_i != -1)
    {
        if (a[a_i] == '0' && b[b_i] == '0')
        {
            carry = 0;
        }
        else if ((a[a_i] == '1' && b[b_i] == '0' && carry == 0) || (a[a_i] == '0' && b[b_i] == '1' && carry == 0) 
                || (a[a_i] == '0' && b[b_i] == '0' && carry == 1))
        {
            carry = 0;
        }
        else if ((a[a_i] == '1' && b[b_i] == '1' && carry == 0) || (a[a_i] == '0' && b[b_i] == '1' && carry == 1) 
                || (a[a_i] == '1' && b[b_i] == '0' && carry == 1))
        {
            carry = 1;
        }
        else if (a[a_i] == '1' && b[b_i] == '1' && carry == 1)
        {
            carry = 1;
        }
        a_i--;
        b_i--;
    }
    size++;
    if (carry)
    {
        if ((a_i == -1 && b_i == -1))
            size++;
        else
        {
            if (a_i == -1)
            {
                while (b_i != -1  && b[b_i] == '1')
                    b_i--;
                if (b_i == -1)
                    size++;
            }
            else
            {
                while (a_i != -1  && a[a_i] == '1')
                    a_i--;
                if (a_i == -1)
                    size++;
            }
        }
    }
    ret = (char *)malloc(sizeof(char) * (size + 1));
    ret[size--] = '\0';
    while (a[a_i + 1])
        a_i++;
    while (b[b_i + 1])
        b_i++;
    carry = 0;
    while (a_i != -1 && b_i != -1)
    {
        if (a[a_i] == '0' && b[b_i] == '0' && !carry)
        {
            ret[size] = '0';
            carry = 0;
        }
        else if ((a[a_i] == '1' && b[b_i] == '0' && !carry) || (a[a_i] == '0' && b[b_i] == '1' && !carry) 
                || (a[a_i] == '0' && b[b_i] == '0' && carry))
        {
            ret[size] = '1';
            carry = 0;
        }
        else if ((a[a_i] == '1' && b[b_i] == '1' && !carry) || (a[a_i] == '0' && b[b_i] == '1' && carry) 
                || (a[a_i] == '1' && b[b_i] == '0' && carry))
        {
            ret[size] = '0';
            carry = 1;
        }
        else if (a[a_i] == '1' && b[b_i] == '1' && carry)
        {
            ret[size]= '1';
            carry = 1;
        }
        a_i--;
        b_i--;
        size--;
    }
    while (a_i != -1)
    {
        if (a[a_i] == '0' && !carry)
        {
            ret[size] = '0';
            carry = 0;
        }
        else if ((a[a_i] == '1' && !carry) || (a[a_i] == '0' && carry == 1))
        {
            ret[size] = '1';
            carry = 0;
        }
        else if (a[a_i] == '1' && carry)
        {
            ret[size] = '0';
            carry = 1;
        }
        a_i--;
        size--;
    }
    while (b_i != -1)
    {
        if (b[b_i] == '0' && !carry)
        {
            ret[size] = '0';
            carry = 0;
        }
        else if ((b[b_i] == '1' && !carry) || (b[b_i] == '0' && carry == 1))
        {
            ret[size] = '1';
            carry = 0;
        }
        else if (b[b_i] == '1' && carry)
        {
            ret[size] = '0';
            carry = 1;
        }
        b_i--;
        size--;
    }
    if (carry)
        ret[size] = '1';
    return (ret);
}

---

Solution 3

(인터넷 참고)

 

시프트와 비트 연산자를 이용한 풀이

 

시프트를 이용해 2일 때와 1, 0일 때를 묶어 처리한다.

 

이후 & 연산을 이용하여 들어갈 숫자를 결정한다.

 

익숙지 않아 다른 문제 풀 때 적용 가능할 수 있을지는 모르겠다.

 

char* addBinary(char* a, char* b) {

    int         i;
    int         j;
    int         k;
    char        *t;
    char        *c;

    i = strlen(a) - 1;
    j = strlen(b) - 1;
    
    if (i < j)
    {
        t = a;
        k = i;
        a = b;
        b = t;
        i = j;
        j = k;
    }
    
    const int   len = i + 1;;
    
    while (i > 0 && j >= 0)
    {
        a[i] += b[j] - '0';
        a[i - 1] += (a[i] - '0') >> 1;
        a[i] = (a[i] & 1) + '0';
        j--;
        i--;
    }
    if (j == 0)
        a[0] += b[0] - '0';
    else
        while (i > 0 && a[i] > '1')
        {
            a[i - 1] += (a[i] - '0') >> 1;
            a[i] = (a[i] & 1) + '0';
            i--;
        }
    if (a[0] > '1')
    {
        c = (char *)malloc(sizeof(char) * (len + 2));
        memcpy(c + 1, a, len);
        c[0] = '0' + ((c[1] - '0') >> 1);
        c[1] = (c[1]&1) + '0';
        c[len + 1] = 0;
        a = c;
    }
    return a;
}

---

총평

아는 만큼 보인다는 말이 적용되는 문제다.

 

지금까지 시프트 연산이나 비트 연산은 사용하지

 

않았기 때문에 엄청 오래 걸렸다.

 

다른 문제 풀 때는 적용 가능한지 꼭 검토해야겠다.