Add Binary

풀이

먼저 십진수 변환은 안됨

문자열의 길이가 $10^4$인데, 즉, $2^{10^4}$라는 뜻이라 숫자 개큼 ㅇㅇ

그래서 차례대로 한자리씩 더하면서 계산하면 됨

먼저 Example 1에서 보이듯이 두 문자열 input의 크기가 다를 수 있으므로,
계산 편의성을 위해 빈 자리를 0으로 채워주도록 함

핵심은 carry라는 올림수임

두 이진수의 각 자리의 합과 carry를 더한 수에 따라 값에 차등을 두면 됨

항상 이진수 연산은 끝자리부터,
연산결과는 항상 마지막에 추가산결과는 항상 마지막에 추가

수행과정은 아래와 같음

a : 10111
b : 11011
이라고 해보자

1. carry = 0
   1+1+carry = 2
   answer = 0...1

2. carry = 1
   1+1+carry = 3
   answer = 01...1

3. carry = 1
   1+0+carry = 2
   answer = 010...1

4. carry = 1
   0+1+carry = 2
   answer = 0100...1

5. carry = 1
   1+1+carry = 3
   answer = 01001...1

남은 carry = 1
따라서 answer의 마지막에 올림수에 해당되는 1을 추가해줌

answer = 010011

뒤집기
answer = 110010

하지만 이는 이진수를 역순으로 연산한 결과라 값이 뒤집혀 있음

그러므로 다시 뒤집어주면됨

class Solution {
public:
    string addBinary(string a, string b) {
        
        int bl = b.size() - 1;
        int al = a.size() - 1;

		//연산 편의를 위한 자리수 맞추기 작업
        while(a.size() < b.size()) a = '0' + a;
        while(b.size() < a.size()) b = '0' + b;

        string s = "";
        int carry = 0;

		//올림수를 이용해 각 자리별로 연산
        for(int i = b.size() - 1; i >= 0; i--)
        {
            int sum = carry + (a[i] - '0') + (b[i] - '0');

            if(sum == 0) 
            {
                s += "0";
                carry = 0;
            }
            else if(sum == 1)
            {
                s+= "1";
                carry = 0;
            } 
            else if(sum == 2)
            {
                s += "0";
                carry = 1;
            }
            else
            {
                s += "1";
                carry = 1;
            }
        }

		//올림수가 남았을 경우, 결과에 추가해주기
        if(carry > 0)
        {
            s += "1";
        }

		//연산결과 뒤집기
        reverse(s.begin(), s.end());
        
        return s;
    }
};

$O(n)$으로 해결!