[python3] 67. Add Binary

풀이 일자: 23.02.14

난이도: [Easy]

분류: [Math, Bit Manipulation]

문제 내용

str형태로 주어지는 이진수 a, b를 합한 결과를 이진수 문자열형태로 리턴하는 문제이다.

 

문제 해결 흐름

 

1. 2진수를 10진수로 바꿔서 더한다음 다시 2진수로 변환하는 방법이 있겠다.

→ int(num, 2)를 사용하면 2진수 형태의 문자열을 10진수로 변환이 가능하며 bin(num)을 사용하면 '0b1111'의 형태의 이진수 문자열을 얻을 수 있다. 0b는 필요없으니까 [2:]를 이용한 slicing을 하면 끝!

 

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a = int(a, 2);
        b = int(b, 2);

        ans = bin(a+b)[2:];        
        return ans

=> Python의 내장함수를 사용한다면 간단하게 해결된다.

 

다른 해결 방식

 

1. 만약에 내장함수를 사용하지 않고 풀어야 한다면 어떤 방식이 있을까?

→ string을 뒤에서부터 비교가면서 직접 2진수 계산과정을 수행하는 방법이 있다,

 

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        
        alen = len(a) - 1;
        blen = len(b) - 1;
        ans = "";
        carry = 0;

        while((alen >=0 and blen >=0) or carry == 1):   # 둘 중 하나가 다 돌면서 carry가 없을때까지
            
            bitsum = 0;
            
            if carry == 1:
                if alen < 0 and blen < 0:               # carry만 존재하는 경우 
                    ans = ans + "1";
                    break;
                else:                                   # carry외에 존재
                    bitsum += carry;
                carry = 0;
            
            if alen < 0:                                # b만 남았을 때(carry가 1일때)
                bitsum += int(b[blen]);
                blen -= 1;
            elif blen < 0:                              # a만 남았을 때(carry가 1일때)
                bitsum += int(a[alen]);
                alen -= 1;
            else:                                       # a,b 둘다 있을 때
                bitsum = bitsum + int(b[blen]) + int(a[alen]);
                alen -= 1;
                blen -= 1;

            if bitsum >= 2:                             # bitsum이 2가 넘어가면 carry발생
                carry = 1;
                ans = ans + str(bitsum - 2);
            else:
                ans = ans + str(bitsum);

        
        if alen >= 0:                                   #a가 남은 경우 남은부분 그대로 붙임
            ans = ans + a[alen::-1];
        elif blen >= 0:                                 #b가 남은 경우 남은부분 그대로 붙임
            ans = ans + b[blen::-1];
        
        return ans[::-1];

=> 2진수의 합 과정을 그대로 구현한 코드

 

 

 

문제 링크

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

Add Binary - LeetCode