LeetCode 67(Add Binary, Python)

1. 문제 링크

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

2. 문제 설명

• 이진법으로 구성된 두개의 문자열 a,b가 주어졌을 때, 두 개의 합을 이진법으로 반환
• 예시) a= "11", b= "1"이면 십진법으로 3+1= 4이고, 이를 다시 이진법으로 반환한 "100"을 반환 

3. 처음 풀이 

• 만약 두 문자열이 0이면 0을 반환,
• 두 문자열을 더한 값을 십진법으로 반환하고 → 다시 이진법으로 변환하는 식으로 풀이
  • "11"과 "1"을 더한 "12"를 십진법으로 변환하면, 2*1 + 1*2^1 = 4
  • 4를 계속 2로 나누면서 이진법으로 변환 
    • result = '' (sum_num = 4)
    • result = '0' (sum_num = 2)
    • result = '00' (sum_num = 1)
    • result = '100' (sum_num = 0) while문 종료

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        
        if a =='0' and b=='0': # 두 문자열이 '0'이면 '0'을 반환
            return '0'
                
        digits = len(str(int(a) + int(b))) - 1 # 두 문자열의 합의 자리수 -1 을 계산 
        sum_num = 0
        
        for i in str(int(a) + int(b)): # 십진법으로 변환한 값을 sum_num에 저장
            sum_num += int(i) * 2 ** digits 
            digits -= 1 
        
        result = ''
        while(sum_num != 0): # 이진법으로 다시 변환 - sum_num이 0이 아닐 때까지 계속 2로 나누면서 result를 concat
            result = str(sum_num % 2) + result
            sum_num = sum_num // 2 

        return result

• runtime beats 93.96% 

4. 다른 풀이 

• 문자열 a,b에 대해 각각십진법으로 변환한 후 → 다시 이진법으로 변환 (본질은 기존 풀이와 같다)

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a_ten=0
        b_ten=0
        c_bin=''

        for i in a:
            a_ten=2*a_ten+int(i)

        for i in b:
            b_ten=2*b_ten+int(i)

        c_ten=a_ten+b_ten

        if c_ten==0:
            return '0'

        while c_ten>=1:
            c_bin=str(c_ten%2)+c_bin
            c_ten=c_ten//2
        
        return c_bin

5. 배운 점 

• 이진법 ↔ 십진법 변환 방법만 잘 알면 직관적으로 해결 가능한 문제