Leetcode Java Add Binary

업데이트:

문제

Link

코드

class Solution {

  public String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int aIdx = a.length() - 1;
    int bIdx = b.length() - 1;
    int carry = 0;
    while(aIdx >= 0 || bIdx >= 0) {
      int sum = carry;
      if (aIdx >= 0) {
        sum += a.charAt(aIdx--) - '0';
      }
      if (bIdx >= 0) {
        sum += b.charAt(bIdx--) - '0';
      }
      sb.append(sum % 2);
      carry = sum / 2;
    }
    return (carry == 1 ? sb.append(carry) : sb).reverse().toString();
  }

}

결과

Link

설명

  1. 주어진 두 이진수로 이루어진 문자열 a와 b를 더한 값을 문자열로 반환하는 문제이다.

  2. 주어진 문제를 해결하기 위해 기본 변수를 정의한다.
    • 주어진 문자열 a와 b를 합친 결과를 저장할 변수 sb를 정의한다.
      • 동적 문자열의 생성시, 효율적인 메모리 사용을 위해 StringBuilder를 사용한다.
    • 주어진 문자열 a와 b를 역순으로 반복하기 위해 aIdx와 bIdx를 각 문자열의 길이에서 1을 뺀 값으로 정의한다.
    • 두 이진 문자열의 합이 2가 넘어 앞 자리가 증가해야 하는 경우(올림의 경우)를 위해 변수 carry를 정의한다.
  3. aIdx와 bIdx가 하나라도 0 이상일 때 까지 반복하여 주어진 문자열 a와 b의 합을 계산한다.
    • 두 문자열 a와 b의 각 자릿수를 더하기 위해 sum 변수를 정의하고, 해당 값은 직전 값의 올림 값인 carry로 초기화 한다.
    • aIdx가 0 이상일 경우, sum에 a의 aIdx번째 값을 더해준다.
    • bIdx가 0 이상일 경우, sum에 b의 bIdx번째 값을 더해준다.
      • 위의 두 문자의 정수 값을 사용할 때 char의 int 값은 Ascii code의 값이므로, ‘0’을 빼서 해당 문자의 정수 값을 구하여 사용한다.
    • 위에서 구해진 sum을 이용하여 변수 sb에 $sum \mod 2$의 값을 추가하고, carry에는 $\frac{sum}{2}$의 값을 넣어주어 다음 자리의 계산에 활용한다.
  4. 반복이 종료되고 carry가 1일 경우 변수 sb에 carry값을 추가하고, 그렇지 않은 경우 변수 sb 그대로 문자열을 뒤집어 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.

댓글남기기