67. Add Binary

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

Add Binary - LeetCode

 

틀린 풀이

문자열로 들어오는 해당 값을 십진수로 변경하고 덧셈을 한 결과를 다시 2진수로 변경하는 방법으로 풀이.

문제에서 문자열의 길이의 범위를 주어지지 않아 1차로 풀이하였다.

INPUT으로 들어오는 문자열의 길이의 범이가 INT 유효 범위가 넘어서 오답이 됨.

문자열이 입력으로 들어오는 문제에서는 정수 유효 범위 등을 한 번 더 생각하자.

 

class Solution {
public:
    long long to_demical(string a) {

        long long result = 0;

        for (int i = 0; i < a.size(); i++) {
            int code = a[i] - '0';

            // 1 일 때만 2 의 제곱을 더해준다
            if(code) {
                result = result + pow(2, a.size()-1 - i);
            }
        }
        return result;
    }

    string to_binary(long long n) {

       	if (n == 0) {
		    return "0";
	    }
        
        string s;

        while (n) {
            long long cand = n % 2;
            if (cand == 1) {
                s.push_back('1');
            }
            else {
                s.push_back('0');
            }
            n = n / 2;
        }

        reverse(s.begin(), s.end());
        return s;
    }
    
    string addBinary(string a, string b) {
        long long demical_a = to_demical(a);
        long long demical_b = to_demical(b);

        long long cand = demical_a + demical_b;
        return to_binary(cand);
    }
};

 

Bruth-Force 풀이

A [i] + B [i]의 합이 carry 가 존재할 때에 따라 재 계산하는 로직을 추가하여 노가다로 풀이.

좀 더 쉽게 푸는 방법은 없으려나..

 

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

        int a_size = a.size();
        int b_size = b.size();

        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        const int size = min(a_size, b_size);
        bool carry = false;
        string s;
        for (int i = 0; i < size; i++) {
            if (carry) {
                if (a[i] =='1' && b[i] == '1') {
                    carry = true;
                    s.push_back('1');
                }
                else if (a[i] == '0' && b[i] == '0') {
                    carry = false;
                    s.push_back('1');
                }
                else {
                    carry = true;
                    s.push_back('0');
                }

            }
            else {

                if (a[i] == '1' && b[i] == '1') {	
                    carry = true;
                    s.push_back('0');
                }
                else if(a[i] == '0' && b[i] =='0') {
                    carry = false;
                    s.push_back('0');
                }
                else {
                    carry = false;
                    s.push_back('1');
                }
            }
        }

        int diff = abs(a_size - b_size);

        if (a_size > b_size) {
            for (int i = b_size; i < a_size; i++) {
                if (carry) {
                    if (a[i] == '1') {
                        carry = true;
                        s.push_back('0');
                    }
                    else {
                        carry = false;
                        s.push_back('1');
                    }
                }
                else {
                    if (a[i] == '1') {
                        carry = false;
                        s.push_back('1');
                    }
                    else {
                        carry = false;
                        s.push_back('0');
                    }
                }
            }
        }
        else {
            for (int i = a_size; i < b_size; i++) {
                if (carry) {
                    if (b[i] == '1') {
                        carry = true;
                        s.push_back('0');
                    }
                    else {
                        carry = false;
                        s.push_back('1');
                    }
                }
                else {
                    if (b[i] == '1') {
                        carry = false;
                        s.push_back('1');
                    }
                    else {
                        carry = false;
                        s.push_back('0');
                    }
                }
            }
        }

        if (carry) {
            s.push_back('1');
        }

        reverse(s.begin(), s.end());

        return s;
    }
};

 

W 풀이

모듈화가 좋은듯 합니다.

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    int max(int a, int b) {
        return a > b ? a : b;
    }

    int min(int a, int b) {
        return a > b ? b : a;
    }

    int toInt(char c) {
        if (c == '1')
            return 1;
        return 0;
    }

    char toChar(int a) {
        if (a == 0)
            return '0';
        return '1';
    }

    int f(string &str, int a, int b, int c) {
        int t = a ^ b ^ c;
        str += toChar(t);

        // a, b, c  : [0, 1]
        int carry = (a & b) | (b & c) | (c & a);
        return carry;
    }

    void reverse(string &s) {
        int size = s.size();
        string t(s);
        for (int i = 0; i < size; ++i) {
            s[i] = t[size - 1 - i];
        }
    }


    string addBinary(string a, string b) {
        string s1, s2, str;
        if (a.size() > b.size()) {
            s1 = a;
            s2 = b;
        }
        else {
            s1 = b;
            s2 = a;
        }

        int max_s = s1.size();
        int min_s = s2.size();

        reverse(s1);
        reverse(s2);

        int c = 0;
        for (int i = 0; i < min_s; ++i) {
            int i1 = toInt(s1[i]);
            int i2 = toInt(s2[i]);
            c = f(str, i1, i2, c);
        }
        
        for (int i = min_s; i < max_s; ++i) {
            int i1 = toInt(s1[i]);
            c = f(str, i1, 0, c);
        }

        if (c)
            str += toChar(c);

        reverse(str);
        return str;
    }
};

int main() {
    Solution s;

    string s1, s2;
    cin >> s1;
    cin >> s2;
    string str = s.addBinary(s1, s2);
    return 0;
}

 

O 풀이

간결하게 잘 풀었습니다.

class Solution {
public:
    string addBinary(string a, string b) {
        string strSum;
        
        int nASize = a.length();
        int nBSize = b.length();
        int nAPos = nASize;
        int nBPos = nBSize;
        
        int nC = 0;
        do
        {            
            int nA = 0;
            int nB = 0;
            if( nAPos > 0 )
                nA = (a[--nAPos] -'0') % 2;
            if( nBPos > 0 )
                nB = (b[--nBPos] -'0') % 2;
            
            int nSum = nA + nB + nC;
            strSum.insert(strSum.begin(), '0' + nSum % 2);
            nC = nSum > 1 ? 1 : 0;
            
        }while( nAPos || nBPos || nC );      
        
        return strSum;        
    }
};

 

C 풀이

ㅇㅅㅇ

class Solution {
public:
    string addBinary(string a, string b) {
        string ret;
        int cur;
        int carry = 0;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        for (int i = 0; i < min(a.size(), b.size()); ++i) {
            cur = (a[i] - '0') + (b[i] - '0') + carry;
            if (cur > 1) {
                cur %= 2;
                carry = 1;
            } else {
                carry = 0;
            }
            char chCur = cur + '0';
            ret.push_back(chCur);
        }
        if (a.size() > b.size()) {
            for (int i = b.size(); i < a.size(); ++i) {
                cur = (a[i] - '0') + carry;
                if (cur > 1) {
                    cur %= 2;
                    carry = 1;
                } else {
                    carry = 0;
                }
                char chCur = cur + '0';
                ret.push_back(chCur);
            }
        } else if (a.size() < b.size()) {
            for (int i = a.size(); i < b.size(); ++i) {
                cur = (b[i] - '0') + carry;
                if (cur > 1) {
                    cur %= 2;
                    carry = 1;
                } else {
                    carry = 0;
                }
                char chCur = cur + '0';
                ret.push_back(chCur);
            }
        } 
        if (carry == 1)
            ret.push_back('1');
        reverse(ret.begin(), ret.end());
        return ret;
    }
};