[LeetCode/Python] 67. Add Binary

문제 링크: https://leetcode.com/problems/add-binary/description/?envType=study-plan-v2&envId=top-interview-150

 

숫자로 쉽게 치환해서 패키지를 써서 이진법 덧셈을 할 생각이었는데, string 자체로 풀어보고 싶다고 생각했다.

 

 

[내 풀이]

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # without converting string to int
        carry = 0
        i, j = len(a) - 1, len(b) - 1

        result = []
        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                carry += int(a[i])
                i -= 1

            if j >= 0:
                carry += int(b[j])
                j -= 1
            
            result.append(str(carry % 2))
            carry //= 2
        
        return ''.join(reversed(result))

 

처음에 length를 각각 둘 생각을 하지 못해서 좀 애를 먹었으나, 각각 두고 while문을 쓰면 될 것 같다는 생각을 하자마자 빠르게 풀렸다.

그리고 오랜만에 써보는 별거없지만 python 스러운 문법들!

 

 

[다른 풀이]

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

 

bin 메서드로 쉽게 풀어버리기~

 

 

시간 복잡도

각 문자열의 길이를 m, n이라고 했을 때

O(max(m, n))