[Java] LeetCode 67 : Add Binary

LeetCode # 67

---

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

 

 

Example 1:

 

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

 

Constraints:

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

---

Wrong Solution #1

class Solution {
    public String addBinary(String a, String b) {
        long result = convert(a) + convert(b);

        if (result == 0) return "0";

        StringBuilder builder = new StringBuilder();

        while (result > 0) {
            builder.append(result % 2);
            result /= 2;
        }

        return builder.reverse().toString();
    }

    private long convert(String s) {
        int i = s.length() - 1;
        int result = 0;
        while (i >= 0) {
            result += Math.pow(2, s.length() - 1 - i) * (s.charAt(i) - 48);
            i--;
        }
        return result;
    }
}

 

Result #1

💡 2진수를 10진수로 변환하는 방법은 틀렸다.

가장 직관적으로 생각할 수 있는 방법은 2진수를 10진수로, 10진수를 2진수로 변환하여 풀이하는 것이다.

하지만 이 방법은 틀렸다. 자료형의 범위때문에 잘못된 값이 출력된다.

---

Solution #2

class Solution {
    public String addBinary(String a, String b) {
        int i = a.length() - 1;
        int j = b.length() - 1;

        int sum = 0;
        StringBuilder builder = new StringBuilder();

        while (sum > 0 || i >= 0 || j >= 0) {
            if (i >= 0) {
                sum += a.charAt(i) - '0';
                i--;
            }

            if (j >= 0) {
                sum += b.charAt(j) - '0';
                j--;
            }
            builder.append(sum % 2);
            sum /= 2;
        }

        return builder.reverse().toString();
    }
}

 

Result #2

💡 String a와 b의 인덱스를 다르게 분기하여 계산한다.

a의 길이만큼, b의 길이만큼 인덱스 값을 갖는 변수 i, j를 두어 계산한다.

변수 sum에 값을 더하고, 2로 나눈 나머지 값을 StringBuilder에 append() 한다.

 

---

 

More Algorithm!

 

👇👇

 

github.com/ggujangi/ggu.leet-code

ggujangi/ggu.leet-code

 

 

 

 

출처 : leetCode