프로그래머스 입문 120885 이진수 더하기

문제

출처

0과 1로만 이루어진 두 문자열이 매개변수로 주어진다.
두 이진수를 더한 값을 이진수 문자열로 반환하시오.
단, "0"은 입력으로 들어올 수 있지만 "01"처럼 앞에 불필요한 0이 붙은 값은 들어오지 않는다.

bin1	bin2	result
"10"	"11"	"101"
"1001"	"1111"	"11000"

풀이

char* solution(const char* bin1, const char* bin2)
{
    int bin1_len = strlen(bin1);
    int bin2_len = strlen(bin2);
    int max_len = (bin1_len > bin2_len) ? bin1_len : bin2_len;

    char* result = (char*)malloc(max_len + 2);
    result[max_len + 1] = '\0';

    int carry = 0;
    int bin1_idx = bin1_len - 1;
    int bin2_idx = bin2_len - 1;

    for (int i = max_len; i >= 0; i--)
    {
        int bin1_bit = (bin1_idx >= 0) ? bin1[bin1_idx--] - '0' : 0;
        int bin2_bit = (bin2_idx >= 0) ? bin2[bin2_idx--] - '0' : 0;
        int sum = bin1_bit + bin2_bit + carry;

        result[i] = (sum % 2) + '0';
        carry = sum / 2;
    }

    if (result[0] == '0')
    {
        int trimmed_result_len = max_len + 1;

        char* trimmed_result = (char*)malloc(trimmed_result_len);

        strcpy(trimmed_result, result + 1);
        free(result);

        return trimmed_result;
    }

    return result;
}

덧셈 결과의 길이는 맨 앞자리에서 올림이 발생하는지에 따라 달라진다.
1 + 0은 1이므로 새 자리가 생기지 않는다.
11 + 11은 110이므로 새 자리가 생긴다.
두 입력의 길이만으로는 올림 여부를 확정할 수 없으므로 result는 max_len + 2만큼 할당한다.
확보한 두 칸 중 한 칸은 올림을 대비한 자리이고, 나머지 한 칸은 널 문자를 위한 공간이다.

bin1과 bin2의 길이가 다를 수 있으므로 어느 쪽 길이에 맞춰 반복할지 정해야 한다.
이 코드에서는 올림을 대비한 자리까지 포함해 max_len + 1번 반복한다.
한쪽 입력에 더 이상 읽을 자리가 없으면 해당 값을 0으로 처리한다.
예를 들어 매개변수로 10과 1이 들어오면 최대 길이가 2이고, 올림을 대비해 널 문자를 제외하고 총 3칸을 사용한다.
반복문도 이 3칸에 맞춰 3회 실행되지만, 10과 1은 3자리가 아니다.
이때 부족한 자리는 0으로 처리하므로 실제 계산은 010 + 001을 더하는 방식으로 진행된다.

계산이 끝난 뒤에는 맨 앞에 0이 남을 수 있다.
1 + 1은 10이 되어 문제가 없지만, 10 + 1은 011처럼 앞에 0이 붙는다.
이 경우 앞의 0을 제외한 길이로 다시 동적 할당한 뒤 복사해서 반환한다.

이 코드에서 추가로 생각해볼 부분이 있다.
비트 연산자를 이용하면 sum 변수를 대체할 수 있다.
XOR는 현재 자리에 남을 비트를 구하고, AND는 다음 자리로 넘길 올림을 구한다.

result[i] = (bin1_bit ^ bin2_bit ^ carry) + '0';
carry = (bin1_bit & bin2_bit) | (bin1_bit & carry) | (bin2_bit & carry);