[LeetCode]67. Add Binary

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

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"

이번 알고리즘의 경우 갈피를 잘 잡지 못했다.
이진수의 연산이니 당연히 배열의 마지막 인덱스부터 같이 연산을 해야하는 건 분명한데
1 + 1 일때 다음자리에 1을 추가로 더해준다거나 배열에 저장을 어떤식으로 해야할지 감이 전혀 잡히지 않았다.

• 다른 사람의 코드를 보고 분석했다.

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder(); // String은 불변객체이므로 메모리 동적할당을 하기 위해 Stringbuilder사용
        int i = a.length() -1; 
        int j = b.length() -1; //이진수는 오른쪽부터 계산해야하니까
        int carry = 0;

        while(i>=0 || j>=0){
            int sum = carry;
            if(i>=0)sum += a.charAt(i) - '0'; // char을 int로 변환하기 위해서 '0'으로 빼줌
            if(j>=0)sum += b.charAt(j) - '0'; //똑같이 진행
            sb.append(sum % 2); //0이나 1의 값이 나와야하므로 2로 나눈 나머지를 sb에 저장
            carry = sum /2; //올림 수 이다. 1, 1일 경우 다음자리에 1이 올라가야하므로

            i--;
            j--;
        }

        if(carry != 0)sb.append(carry);
        return sb.reverse().toString();
    }
}

이번 알고리즘 문제에서 알아갈 것은

정수가 char형태로 되어있다면 int로 전환하기 위해서 '0'을 빼주면 된다는 것

String의 경우 동적 할당이 되지 않으므로 배열값을 추가할땐 StringBuilder를 사용하면 된다는 것