[LeetCode]Add Binary

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 두개의 이진수를 더해서 이진수로 출력하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a,2) + int(b,2))[2:]

접근 방법

1. 파이썬을 활용해 손쉽게 풀이할 수 있는 방법입니다.
2. 두 숫자를 int형 변환하여 덧셈을 진행합니다.
3. 그 후 2진수로 변환을 하고 0b를 제거하고 2번째 요소부터 출력합니다.

파이썬의 형 변환을 이용해서 손쉽게 구현할 수 있었지만 순수하게 이진수를 더하는 로직으로도 구현을 해보았습니다.

 

두번째로 시도한 답안

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        answer = ''
        carry = 0

        a_len = len(a)-1
        b_len = len(b)-1

        while a_len >= 0 or b_len >= 0 or carry:
            if a_len >= 0:
                carry += int(a[a_len])
                a_len -= 1
            if b_len >= 0:
                carry += int(b[b_len])
                b_len -= 1

            div, mod = divmod(carry, 2)
            answer += str(mod)
            carry = div

        return ''.join(reversed(answer))

접근 방법

1. 이진수의 올림수를 위해 carry라는 변수를 활용하는 방법입니다.
2. 먼저 주어진 문자열의 길이를 구합니다.
3. 덧셈이 필요한 a나 b가 남아있거나 carry가 남아있는 동안 순회합니다.
   1. 덧셈이 필요한 a가 남아있으면 해당하는 수를 carry에 더하고 a를 1개 감소합니다.
   2. 덧셈이 필요한 b가 남아있으면 해당하는 수를 carry에 더하고 b를 1개 감소합니다.
   3. 더해진 숫자를 2로 나누어서 다음 올림수와 현재 자리에서의 수를 구합니다.
   4. 현재 자리의 수는 answer에 기록하고 나머지 올림수는 carry에 기록합니다.
4. 뒤에서부터 덧셈이 기록되었기 때문에 이를 뒤집어서 출력합니다.

두 이진수를 더하는 방법을 실제로 코드로 표현한 방법입니다. 숫자를 뒤에서부터 더해가면서 2가 넘으면 올림수 처리를 하여 누적해서 더해가는 방법입니다. 한가지 특이한 포인트는 길이가 다른 문자열의 덧셈을 위해서 a와 b의 길이를 감소하면서 0보다 큰 경우에만 carry에 더하면서 진행했다는 점입니다.