[Grind75-LeetCode] Add Binary JAVA

반응형

728x90

[Grind75-LeetCode] Add Binary - Easy

---

접근

• 진수 변환
• 정석 덧셈 구현(?)

---

풀이

문자열로 주어지는 이진수를 덧셈 연산을 수행한 뒤 이진수 값을 다시 문자열로 반환하는 문제이다. 자바의 경우 문자열로 이루어진 각 진수 변환 메서드를 기본적으로 제공하다 보니 사실 통과 자체는 굉장히 쉬운 문제이다. 그런데 주어지는 이진수의 최대 길이가 10000자리로 long 타입을 사용해도 오버플로우가 발생한다. 자바의 BigInteger 라이브러리를 사용해 주면 푸는데 문제는 없으나 처참한 성능을 자랑했다.

하위 16.39% 성능의 코드

//BigInteger 사용 코드
import java.math.BigInteger;

class Solution {
    public String addBinary(String a, String b) {
        BigInteger num1 = new BigInteger(a, 2);
        BigInteger num2 = new BigInteger(b, 2);
        return num1.add(num2).toString(2);
    }
}

그래서 다른 사람들은 어떻게 풀었나 지켜보다 정석적인 이진수 덧셈 연산을 수행한 코드가 있었고 수행 시간은 1ms로 99.85% 상위 0.15%의 성능을 자랑하는 코드를 가져왔다.

public String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    int i = a.length() - 1;
    int j = b.length() - 1;

코드는 StringBuilder를 사용해 하나하나 더 한 값을 쌓아주는 자릿수 덧셈 방식이다. 올림을 표시하는 carry와 연산은 제일 작은 값인 오른쪽부터 수행된다.

    while (i >= 0 || j >= 0 || carry == 1) {
      if(i >= 0)
        carry += a.charAt(i--) - '0';
      if(j >= 0)
        carry += b.charAt(j--) - '0';
      sb.append(carry % 2);
      carry /= 2;
    }

연산은 숫자가 남아있거나 마지막 연산에서 캐리가 발생해 캐리 값이 1인 경우 반복되게 된다. 연산의 주 내용은 어느 더하기와 같이 작은 값부터 수행하여 이진수 문자열의 마지막 인덱스부터 0번 인덱스까지 진행되고 문자값 '0'을 빼주어 숫자로 만든 뒤 carry에 더해준다. 각 자릿수를 합한 carry에 2를 나눈 나머지 값을 더해진 값으로 추가해 주고 carry를 2로 나누어 준다. 2로 나누는 과정은 올림 값이 있는지 확인하는 것으로 더해진 이진수의 각 자리가 1로 carry값이 2가 되었다면 올림이 발생하여 해당 자리는 0으로 추가되고 carry는 1로 앞자리 값에 더해지게 된다.

return sb.reverse().toString();

그리고 연산 순서가 마지막 자리부터 수행하여 문자열 순서와는 반대이므로 역순으로 변경한 뒤 반환한다.

성능

---

전체 코드

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

    while (i >= 0 || j >= 0 || carry == 1) {
      if(i >= 0)
        carry += a.charAt(i--) - '0';
      if(j >= 0)
        carry += b.charAt(j--) - '0';
      sb.append(carry % 2);
      carry /= 2;
    }
    return sb.reverse().toString();
  }
}

이렇게 단순 6배의 성능차이가 나지만 이미 구현되어 있는 메서드가 너무 간편하기에 큰 문제가 없다면 간단한 쪽을 사용하지 싶다. 

---

코드 출처: https://leetcode.com/problems/add-binary/solutions/3183205/1ms-beats-100-full-explanation-append-reverse-c-java-python3