Leetcode - 67. Add Binary - Easy

오늘 문제의 입력값은 두개의 String 타입인데 그 값은 이진수 입니다.

이 두 값을 이진수로 더한 값을 리턴하면 됩니다.

 

이 문제를 풀기에 앞서서 이 두 메소드를 살펴 보겠습니다.

Integer.parseInt(String, n), toBinaryString(int num)

 

우선 parseInt(String s, int radix)를 알아보겠습니다.

 

여기서 String s는 숫자로만 구성 되어야 합니다. 그런데 그 타입이 String 인 것입니다.

Int radix는 그 스트링 으로 돼 있는 숫자가 몇 진수 인지를 나타내는 겁니다.

 

그리고 그 값을 10진수 형태로 반환하는데 이 메소드가 하는 역할 입니다.

 

 

toBinaryString(int num) 은 숫자를 입력값을 받아서 그것을 진수로 바꿔서 이것을 String 타입으로 반환하는 겁니다.

 

그러니까 위 문제에서 요구한 두개의 스트링 입력값을 받아서 그것을 더한 후 그 이진수를 스프링으로 반환하는 것은 이 한 줄이면서 간단하게 해결 됩니다.

 

    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));

 

Integer.parseInt(a,2)는 입력받은 이진수 a를 10진수로 바꿉니다.

Integer.parseInt(b.2)는 입력받은 이진수 b를 10진수로 바꿉니다.

그리고 이 두 값을 더한 후 toBinaryString()이 다시 이진수로 만들고 이것을 String 타입으로 변환해서 반환합니다.

 

그러면 이 문제에 대한 해답이 될 수 있습니다. 그런데 여기에서 문제가 있습니다.

 

이렇게 하면 자릿수가 많은 입력값은 NumberFormatException이 발생합니다.

 

String을 numeric type으로 변환하는데 있어서 적당한 포맷이 없기 때문에 일어나는 예외 입니다.

 

Integer, Long, BigInteger 등 모든 Numeric type은 자릿수 제한이 있기 때문입니다.

 

이 문제를 해결하기 위해서는 좀 더 복잡한 로직을 만들어야 합니다.

 

첫번째 방법은 bit 별로 계산하는 겁니다.

 이진수에서 1+1 은 10 이 됩니다.

1+0 = 1, 0+0 은 0이 되구요.

이렇게 그냥 비트 단위에서 계산하는 겁니다.

 

이것을 코딩하면 아래와 같이 됩니다.

 

class Solution {
  public String addBinary(String a, String b) {
    int n = a.length(), m = b.length();
    if (n < m) return addBinary(b, a);
    int L = Math.max(n, m);

    StringBuilder sb = new StringBuilder();
    int carry = 0, j = m - 1;
    for(int i = L - 1; i > -1; --i) {
      if (a.charAt(i) == '1') ++carry;
      if (j > -1 && b.charAt(j--) == '1') ++carry;

      if (carry % 2 == 1) sb.append('1');
      else sb.append('0');

      carry /= 2;
    }
    if (carry == 1) sb.append('1');
    sb.reverse();

    return sb.toString();
  }
}

 

입력 받은 두 값 중 자릿수가 큰 입력값의 크기 만큼 for 문을 돌립니다.

For 문 안에는 이진수 계산법을 하는 로직을 있습니다.

이렇게 비트 단위로 계산 한 후 결과 값을 리턴 하는 방법이 첫번째 방법입니다.

 

두번째 방법은 XOR로 처리한 후 carry하는 방법입니다.

알고리즘은 아래와 같습니다.

 

스크립트는 아래와 같습니다.

 

import java.math.BigInteger;
class Solution {
  public String addBinary(String a, String b) {
    BigInteger x = new BigInteger(a, 2);
    BigInteger y = new BigInteger(b, 2);
    BigInteger zero = new BigInteger("0", 2);
    BigInteger carry, answer;
    while (y.compareTo(zero) != 0) {
      answer = x.xor(y);
      carry = x.and(y).shiftLeft(1);
      x = answer;
      y = carry;
    }
    return x.toString(2);
  }
}

 

참고로 이것을 Python으로 하면 아래와 같습니다.

 

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]

 

첫번째 방법과 두번째 방법의 Runtime과 Memory 차이는 이렇습니다.

 

솔직히 저로서는 두번째 방법은 자세하게 이해하기는 힘드네요.

그냥 이렇게 있구나 하는 정도로 이해하고 넘어 가기로 했습니다.