LeetCode Add Binary (JavaScript)

링크 : https://leetcode.com/problems/add-binary/description/

문제 설명

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.

---

문제 풀이

1. a, b뒤에서 부터 검사

2. aLen, bLen, carry(자릿수 올림)이 있다면 반복문 진행

• aLen위치 값 + bLen위치 값 + carry의 sum을 구함 (단, 유요한 index일 경우에만 sum에 더하도록)
• 2로 나눈 나머지를 자릿수 올림 값으로 지정
• answer에 sum을 2로 나눈 나머지와 연결

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let aLen = a.length - 1;
    let bLen = b.length - 1;

    let carry = 0;
    let answer = '';
    while (aLen >= 0 || bLen >= 0 || carry) {
        let sum = carry;
        if (aLen >= 0) {
            sum += parseInt(a[aLen--]);
        }
        if (bLen >= 0) {
            sum += parseInt(b[bLen--]);
        }

        carry = Math.floor(sum / 2);
        answer = `${sum % 2}${answer}`;
    }

    return answer;
};

---

결론

a와 b의 length가 10^4이기 때문에 일반 적인 정수 덧셈으로는 해결이 불가능 (overflow 발생)

• 2진수 -> 10진수 정수로 바꾸기 `parseInt(numString, 2)`
• 10진수 -> 2진수 문자열로 바꾸기 `num.toString(2)`

따라서 문자열로 각 자릿수를 합하고 carry를 이용하여 문자열을 만들어나가는 형식으로 해결