[LeetCode] Add Binary

문제 링크

Can you solve this real interview question? Add Binary - 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.

https://leetcode.com/problems/add-binary/

문제 요구 조건

두 바이너리수를 문자열로 받게되요.

두 바이너리의 합을 바이너리 문자열로 반환 해야되요.

저의 문제 풀이

결론적으로 풀지 못했어요. 아래의 코드는 제가 이렇게 풀려고 노력해봤다는 과정을 보여주는 것이고, 미완성인 코드라 굳이 코드를 읽어보시지 않으셔도 될 것 같아요.

저의 문제풀이

JavaScript

var addBinary = function (a, b) {
    const alast = a.length - 1;
    const blast = b.length - 1;
    let result = [];
    const isALonger = alast > blast;

    for (let i = 0; i <= isALonger; i++) {
        if (blast - i < 0 || alast - i < 0) {
            break;
        } else if ((a[alast - i] + b[blast - i]) === 2) {
            result.unshift(1, 0);
            

        } else {
            reuslt.unshift(1)
        }
    }
};

그럼 바로 정답풀이로 넘어가보도록 할게요.

정답 문제 풀이

정답을 보면 저에게 부족했다고 생각되는 부분은 두 수의 합이 2가 되었을 때 올림수를 어떻게 넘겨줄지에 대한 부분이었는데, 풀이엔 carry라는 변수를 사용해서 while문으로 다음 순회로 넘겨주는 방식을 사용했더라구요. 그리고 result라는 문자열을 remainder(%)를 활용해서 새로운 문자로 new + old 이런 식으로 재조합하는 방식을 사용했어요.

저는 문자열 자체를 배열로 만들어 unshift함수를 사용하려 했지만, string을 기본 개념이 부족했는지 저렇게 해볼려고 생각을 못했던 것 같아요. 다음은 정답 코드에요.

정답 풀이 시간 (3ms)

JavaScript

var addBinary = function(a, b) {
    let result = '';
    let i = a.length - 1;
    let j = b.length - 1;
    let carry = 0;

    // 두 문자열 중 하나라도 끝에 도달하지 않았거나 올림수가 남아있을 때까지 반복
    while (i >= 0 || j >= 0 || carry > 0) {
        // 현재 자릿수의 숫자들을 더함
        let sum = carry;
        if (i >= 0) {
            sum += parseInt(a[i]);
            i--;
        }
        if (j >= 0) {
            sum += parseInt(b[j]);
            j--;
        }

        // 합의 나머지를 결과에 추가 (0 또는 1)
        result = (sum % 2) + result;

        // 합의 몫을 다음 올림수로 저장
        carry = Math.floor(sum / 2);
    }

    return result;
};

풀이는 다음과 같아요.

마지막 인덱스와 함께 result와 올림수로 사용할 carry를 초기화해요.

while문의 조건으로 두 인덱스가 0이 이상일 때와 올림수가 존재할 때만 while문 순회를 해요

두 수의 인덱스를 정수로 치환하여 두 합을 sum에 할당해요

remainder(%) 를 통해서 현재 자리의 수를 구하고, 나눗셈의 몫으로 올림수 carry에 할당해서 다음 순회로 넘겨요

최고의 성능을 낸 문제풀이

최고의 성능을 낸 문제풀이를 보니 좀 더 신세계였네요. 항상 틀려도 배우는 게 많다는 것을 또 배웁니다. 최고의 성능을 낸 문제풀이는 BigInt를 사용하는 방식이었네요.

최고의 성능을 낸 문제 풀이 (0ms)

JavaScript

var addBinary = function(a, b) {
    let x=BigInt('0b'+a);
    let y=BigInt('0b'+b);
    return (x+y).toString(2);
};

이 코드에서 배울 수 있는 점은 다음과 같습니다.

BigInt로 변환

BigInt(’0b’ + a) 이 구문을 사용하면 컴퓨터는 문자열 a를 이진수로 인식하고 BigInt객체로 변환합니다. 여기서 ‘0b' 는 Javascript에서 이진수를 나타내는 접두사에요.

BigInt 덧셈

Javascript의 BigInt는 일반적인 숫자와 마찬가지로 덧셈을 할 수 있어요. BigInt를 사용해서 자릿수 제한없이 계산할 수 있어요.

이진수 문자열 변환

BigInt에 내장된 toString(2) 메서드는 숫자를 원하는 진법의 문자열로 변환시킬 수 있는 함수를 제공해요. 이 처럼 매개변수로 2 를 전달하면 BigInt값을 이진수 문자열로 변환해줘요.

느낀점

물론 문제는 틀렸지만, 한 문제를 푸는 데 있어서 정말 여러가지 방식으로 문제해결이 가능하다는 진리를 체감하게 된 문제라고 할 수 있었어요. 제가 이번 문제로 배우게 된 것은 다음과 같아요.

올림수 사용법

string을 unshift처럼 조합하기

BigInt로 이진수 객체 만들기

BigInt의 toString() 메서드로 정수를 이진수 문자열로 변환하기

문제를 틀려도 매일 매일 문제해결 방식의 경험을 쌓아가며 나날이 성장하는 개발자가 되겠습니다 !