[leetcode #67] Add Binary

Problem

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

Example 1:

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

Example 2:

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

Constraints:

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

Idea

이진수를 더하는 원리만 알면 쉽게 풀 수 있는 문제다.

주어진 string a와 b의 길이가 다를 수 있으므로 더 짧은 string의 앞에 0을 붙여넣은 뒤 계산을 했다. (각 string의 index를 개별로 가져가서 계산하는 방법도 좋다.)

계산할 때는 두 숫자의 상태, carry 값에 따라 응답으로 던질 character값과 carry를 조정했다.

코드는 복잡하지만 이렇게 하면 integer와 string 간의 변경이 없어 빠른 시간 내 연산을 처리할 수 있다.

Solution

class Solution {
    public String addBinary(String a, String b) {
        boolean carry = false;

        int len = Math.max(a.length(), b.length());
        String original = (len > a.length()) ? b : a;
        String replaced = (len > a.length()) ? a : b;
        StringBuilder sb = new StringBuilder();
        for (int i=0; i < len - replaced.length(); i++) {
            sb.append('0');
        }
        sb.append(replaced);
        replaced = sb.toString();

        StringBuilder res = new StringBuilder();
        for (int i=len-1; i >=0; i--) {
            if (original.charAt(i) == '1' && replaced.charAt(i) == '1') {
                if (carry == true) {
                    res.insert(0, '1');
                }
                else {
                    res.insert(0, '0');
                }
                carry = true;
            } else if (original.charAt(i) == '0' && replaced.charAt(i) == '0') {
                if (carry == true) {
                    res.insert(0, '1');
                }
                else {
                    res.insert(0, '0');
                }
                carry = false;
            } else {
                if (carry == true) {
                    res.insert(0, '0');
                    carry = true;
                }
                else {
                    res.insert(0, '1');
                    carry = false;
                }
            }
        }

        if (carry == true) {
            res.insert(0, '1');
        }

        return res.toString();
    }
}

Reference

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