[leetcode] Add Binary

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

Add Binary - LeetCode

우선 문제부터 간단하게 요약하면,

 

두 string으로 이진법 숫자가 두개 주어지면, 해당 숫자를 더한 string을 return해야 합니다.

 

<Solution>

int로 바꾸는 등의 방법을 간단하게 생각 해 볼 수 있지만, 문제를 읽어보면, 이진수의 길이가 10^4 까지가 가능합니다. 

 

만약 int로 변형하거나 하게 되면, overflow가 발생할 것임을 알 수 있습니다. 그렇다면, string으로 그대로 처리해야 하는 것을 알  수 있습니다.

 

매번 같은 자릿숫자를 보고 더한다음, 해당 자릿수가 0,1중 어떤 것이고, 위로의 다음 자릿수로의 carry가 있는지로 판단하면 됩니다. 

 

실제 구현은 아래와 같습니다. 아랫자리 부터 계산을 하고, 윗자리 숫자부터 출력을 해야하므로 나중에 들어온 원소가 먼저 나오는 stack자료구조를 사용하면 좀더 쉽게 구현할 수 있습니다. 

 

class Solution {
public:
    string addBinary(string a, string b) {

        int lenA = a.length();
        int lenB = b.length();

        int tmp = 0;
        string retString = "";
        stack <char> retStack;
        for(int i = 0; i<min(lenA, lenB); i++){
            retStack.push((char)((a[lenA-1-i] + b[lenB-1-i] + tmp) % 2 + '0'));
            // update tmp
            tmp = (a[lenA-1-i]-'0' + b[lenB-1-i]-'0' + tmp) / 2;
        }

        // for left over, put it in
        if(lenA > lenB){
            for(int i = 0; i<lenA-lenB; i++){
                retStack.push((a[lenA-1 - lenB - i] + tmp) % 2 + '0');
                tmp = (a[lenA-1 - lenB - i] - '0' + tmp) / 2;
            }
        }
        if(lenB > lenA){
            for(int i = 0; i<lenB-lenA; i++){
                retStack.push((b[lenB-1 - lenA - i] + tmp) % 2 + '0');
                tmp = (b[lenB-1 - lenA - i] - '0' + tmp) / 2;
            }
        }
        // if tmp left
        if(tmp == 1) retStack.push('1');
        // build retString
        while(!retStack.empty()){
            retString += retStack.top(); retStack.pop();
        }
        return retString;
    }
};