[ LeetCode - 67 ] Add Binary

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

Add Binary - LeetCode

문제 보고서 제공되는 라이브러리 사용해서 그냥 넘어가고싶은 마음이 굴뚝 같았다 ㅋㅋㅋ..

그래도 대충 어떻게 풀어야지 감만 갖고 있는 것 보다 직접 푸는게 당연히 도움이 되겠지 싶어서 출발~

---

[ 📌 풀이 ]

• 주어진 배열을 그대로 사용해서 두 수를 더해서 올림이 일어나면 carry 비트를 세팅해주면서 문자열 끝까지 연산한다.
• 신경쓴 부분은 두 문자열의 길이가 다를 때인데 함수를 통해서 아직 인덱스가 문자열 순회를 마치지 못했다면 마저 마무리 하도록 했다.

단순히 비트 연산이라 carry만 신경써주면 크게 문제는 없는것 같다.

0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 0 (carry)

---

[ 📌 코드 - Python(sol1) ]

"""
# Author    : Lee In Bok 
# Date      : 2023.11.04(Sat)
# Spend Time: 47m 50s
# Runtime   : 37 ms (Beats 81.76%)
# Memory    : 16.2 MB (Beats 81.11%)
# Algoritm  : String
"""

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        carry, result = False, []
        x, y = len(a) - 1, len(b) - 1

        if a == b == "0":
            return "0"

        while 0 <= x and 0 <= y:
            if a[x] == b[y] == "1":
                result.append("1" if carry else "0")
                carry = True
            elif a[x] == b[y] == "0":
                result.append("1" if carry else "0")
                carry = False
            else:
                result.append("0" if carry else "1")
                carry = True if carry else False

            x -= 1
            y -= 1
        
        carry = self.checkRest(a, x, carry, result)
        carry = self.checkRest(b, y, carry, result)

        if result[-1] == "0" or carry:
            result.append("1")

        return ''.join(reversed(result))
    
    def checkRest(self, arr, idx, carry, result):
        while 0 <= idx:
            if arr[idx] == "1":
                result.append("0" if carry else "1")
                carry = True if carry else False
            else:
                result.append("1" if carry else "0")
                carry = False

            idx -= 1

        return carry

[ 📌 코드 - Python(sol2) ]

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        return bin(int(a, 2) + int(b, 2))[2:]

[ 📌 다른 사람 코드 - Python]

이렇게 생각이 닿지 않아서 전혀 생각하지 못했던 방법인데 코드도 짧지만 정말 깔끔한거 같다.

나는 문자열 길이가 다를때 어떻게 처리할지도 고민 했었는데 carry를 정수로 두고 같이 해결하는 모습에서 배웠다.

class Solution:
  def addBinary(self, a: str, b: str) -> str:
    s = []
    carry = 0
    i = len(a) - 1
    j = len(b) - 1

    while i >= 0 or j >= 0 or carry:
      if i >= 0:
        carry += int(a[i])
        i -= 1
      if j >= 0:
        carry += int(b[j])
        j -= 1
      s.append(str(carry % 2))
      carry //= 2

    return ''.join(reversed(s))

[ 📌 코드 - Java ]

/**
* Author    : Lee In Bok 
* Date      : 2023.11.04(Sat)
* Spend Time: 47m 50s
* Runtime   : 2 ms (Beats 55.51%)
* Memory    : 41 MB (Beats 70.52%)
* Algoritm  : String
 */


import java.util.ArrayList;
import java.util.List;

public class Q67_AddBinary {
    public static void main(String[] args) {
        Solution s = new Solution();
        String result = s.addBinary("1010", "1011");

        System.out.println(result);
    }
}

class Solution {

    public final String ZERO = "0";
    public final String ONE = "1";

    public String addBinary(String a, String b) {
        if(a.equals(ZERO) && b.equals(ZERO)){
            return a;
        }

        boolean carry = false;
        List<String> result = new ArrayList<>();
        int x = a.length() - 1;
        int y = b.length() - 1;

        while(0 <= x && 0 <= y){
            if(a.charAt(x) == '1' && b.charAt(y) == '1'){
                result.add(carry ? ONE : ZERO);
                carry = true;
            } else if(a.charAt(x) == '0' && b.charAt(y) == '0'){
                result.add(carry ? ONE : ZERO);
                carry = false;               
            } else {
                result.add(carry ? ZERO : ONE);
                carry = carry ? carry : false;
            }

            x--;
            y--;
        }

        carry = checkrest(a, x, carry, result);
        carry = checkrest(b, y, carry, result);

        if(carry || result.get(result.size() - 1).equals(ZERO)){
            result.add(ONE);
        }

        StringBuilder sb = new StringBuilder();

        for(String c : result){
            sb.append(c);
        }

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

    public boolean checkrest(String s, int idx, boolean carry, List<String> result){
        while(0 <= idx){
            if(s.charAt(idx) == '1'){
                result.add(carry ? ZERO : ONE);
                carry = carry ? carry : false;
            } else {
                result.add(carry ? ONE : ZERO);
                carry = false;
            }
            idx--;
        }

        return carry;
    }
}

 

물론 자바의 경우도 제공해주는 라이브러리가 있지만 문자열 길이가 길어지면 통과할 수 없다.

class Solution {
    public String addBinary(String a, String b) {
        return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
    }
}

[ 문자열 길이가 길어질 때 예외 케이스 ]

캐스팅 하기에 범위를 초과하는 값이 들어와서 NumberFormatException 발생한다.

---

[ 📌 결과 - Python ]

[ Result - Python ]

[ 📌 결과 - Java ]

[ Result - Java ]