[LeetCode] Add Binary (java)

문제

 

Given two binary strings a and b, return their sum as a binary string.

 

---

문제[번역]

 

두 이진 문자열 a,b가 주어질때 이진 문자열로 합을 출력하라

 

 

---

 

Example 1:

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

Example 2:

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

 

 

---

제약조건

 

• 1 <= a.length, b.length <= 10^4
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

 

 

 

---

접근방법

 

처음에 Integer.parseInt(값,2) 와 toBinaryString(값)을 이용하여 풀려고 했으나 각 이진 문자열의 길이가 10^4이므로 매우 큰 숫자가 들어와서 실패 하였습니다.

 

이 문제를 푸는 방법은

1. BigInteger 사용

 

or

 

2. carry값 이용하기

carry가 나올 수 있는 경우의 수는

1 + 1 = carry(1)

0과 1이므로 총2가지 경우고

이진수 합의 경우의 수는

carry + 0 + 0 = 1 or 0 (carry가 0 or 1이기 때문)

carry + 0 + 1 = 2 or 1

carry + 1 + 0 = 2 or 1

carry + 1 + 1 = 3 or 1

나올 수 있는 sum 값은 총 0,1,2,3이므로

4가지 경우를 처리해주면 값을 계산할 수 있습니다.

 

 

BigInteger를 사용하면 코드가 매우간결하여 편하지만,

carry를 이용한 방식이 메모리를 적게먹어서 이 방법 또한 좋은 방법이라 생각합니다.

 

 

 

---

코드

import java.math.*;
class Solution {
    public String addBinary(String a, String b) {
        BigInteger numA = new BigInteger(a,2);
        BigInteger numB = new BigInteger(b,2);
        return numA.add(numB).toString(2);
    }
}

 

 

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder stringA = new StringBuilder(a);
        StringBuilder stringB = new StringBuilder(b);
        StringBuilder stringC = new StringBuilder();
        
        stringA.reverse();
        stringB.reverse();
        
        int carry = 0;
        int i = 0;
        int sum;
        while(i < stringA.length() || i < stringB.length()) {
            sum = carry;
            if(i < stringA.length()) 
                sum += stringA.charAt(i) - '0';
            if(i < stringB.length()) 
                sum += stringB.charAt(i) - '0';
            
            switch(sum) {
                case 0:
                    stringC.append('0');
                    break;
                case 1:
                    stringC.append('1');
                    if(carry == 1) carry = 0;
                    break;
                case 2:
                    stringC.append('0');
                    carry = 1;
                    break;
                case 3:
                    stringC.append('1');
                    carry = 1;
                    break;
            }
            i++;
        }
        
        if(carry == 1)
            stringC.append('1');
        
        return stringC.reverse().toString();
        
    }
}

 

---

주의사항

 

이진수 엄청 큰값 들어옴....