[LeetCode] Add Binary

 

 

목차

문제

• 이진수로 표현된 문자열 두 개를 더해 이진수로 표현된 문자열을 반환하는 문제입니다.
• 예시

  • Input: a = "11", b = "1"
    Output: "100"

  • Input: a = "1010", b = "1011"
    Output: "10101"

• 제약조건
  • 1 <= a.length, b.length <= 104
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

문제 풀이

풀이 1 : 십진수로 변환후 다시 이진수로 변환

• 풀이
  • 이진수를 십진수로 변환하고 계산한 뒤에 다시 이진수로 변환하기
• 코드

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

• 시간복잡도
  • 이진수 → 십진수 변환의 시간복잡도는 O(n) 입니다. 모든 이진수 숫자를 탐색하고 십진수로 변환해야 하기 때문입니다.
  • 반대로 십진수 → 이진수 변환의 시간복잡도는 O(logC)입니다. 여기서 C는 십진수의 길이가 아닌 십진수 값 그 자체입니다. 
  • 정수 덧셈의 시간복잡도는 일반적으로 O(1)입니다. 하지만 엄청나게 커다란 숫자의 경우 더해지는 과정은 비트수로 연산되기 때문에 O(logC)가 될 것입니다. (여기서 C는 더해지는 숫자 중 큰 숫자입니다.)
  • 따라서 전체 시간복잡도는 O(n+m+logC)가 될것입니다.

알게 된 내용

• 10진수 2진수로 변환하기

  • b = bin(16)
    print(b)
    # 0b10000

• 2진수 10진수로 변환하기

  • a = int("0b10000", 2)
    print(a)
    # 16
    
    a = int("10000", 2)
    print(a)
    #16

출처

• https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-string/1160/