67. 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 <= 10⁴
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

Submitted Code

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        longer_str = max(len(a), len(b))  # 더 긴 문자열의 길이 측정
        a = a.zfill(longer_str)           # 길이가 longer_str만큼 될 때까지 앞에 0을 추가(두 문자열의 길이 통일)
        b = b.zfill(longer_str)
        
        carry = "0"                       # 자리 올림 저장
        result = ""                       # 결과 저장
        
        for i in range(longer_str - 1, -1, -1):
            total = carry + a[i] + b[i]

            if total == "111":
                result = "1" + result
                carry = "1"
            elif total == "110" or total == "101" or total == "011":
                result = "0" + result
                carry = "1"
            elif total == "100" or total == "010" or total == "001":
                result = "1" + result
                carry = "0"
            elif total == "000":
                result = "0" + result
                carry = "0"
        
        if carry == "1":
            result = "1" + result
        
        return result

Runtime: 5 ms | Beats 41.93%
Memory: 12.51 MB | Beats 8.30%

문자열을 정수로 변환하지 않고 풀어볼 수 있을까 궁금해서 여러 가지로 고민했는데 모두 효율이 좋지 않았다. 다른 답변들을 봐도 다 형변환을 사용했기 때문에, 별로 중요하지 않은 부분이었음을 알았다.

class Solution(object):
    def addBinary(self, a, b):
        a = int(a, 2)       # 문자열로 표현된 이진수를 정수로 변환
        b = int(b, 2)
        
        sum = bin(a + b)    # 정수끼리 더한 후 다시 이진수 문자열로 변환

        return sum[2:]      # 이진수 문자열의 접두사 '0b'를 제거하고 결과 반환

파이썬의 .int()와 .bin() 함수를 이용하면 쉽게 해결할 수 있다.

Other Solutions

1st

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        carry = 0
        res = []
        
        idxA, idxB = len(a) - 1, len(b) - 1           # a, b의 마지막 인덱스
        
        while idxA >= 0 or idxB >= 0 or carry == 1:   # a나 b에 자릿수가 남아있거나 올림값이 있으면 진행
            if idxA >= 0:
                carry += int(a[idxA])   # a의 현재 자리값을 정수로 변환하여 carry에 더하기(이전 올림값에 합산)
                idxA -= 1               # 앞으로 한 칸 이동
            if idxB >= 0:                     
                carry += int(b[idxB])   # b의 현재 자리값을 정수로 변환하여 carry에 더하기(이전 올림값+a에 합산)
                idxB -= 1               # 앞으로 한 칸 이동

            res.append(str(carry % 2))  # 현재 자리값을 계산 후 문자열로 변환하여 결과에 추가(0 또는 1)
            carry = carry // 2          # 다음 자리로 넘길 올림값 계산(2 이상일 경우 올림값이 1이 됨)
            
        return "".join(res[::-1])       # 리스트를 뒤집어서 최종 결과 반환

time complexity: 𝑂(max(𝑚, 𝑛)) ← 각각 len(𝑎)와 len(𝑏)
space complexity: 𝑂(max(𝑚, 𝑛))

현재 자리값은 % 연산으로 구하고, 다음 자리로 넘길 올림값은 // 연산으로 구하는 원리이다.