IT 기술 따라잡기

오늘 문제의 입력값은 두개의 String 타입인데 그 값은 이진수 입니다.

이 두 값을 이진수로 더한 값을 리턴하면 됩니다.

이 문제를 풀기에 앞서서 이 두 메소드를 살펴 보겠습니다.

Integer.parseInt(String, n), toBinaryString(int num)

우선 parseInt(String s, int radix)를 알아보겠습니다.

여기서 String s는 숫자로만 구성 되어야 합니다. 그런데 그 타입이 String 인 것입니다.

Int radix는 그 스트링 으로 돼 있는 숫자가 몇 진수 인지를 나타내는 겁니다.

그리고 그 값을 10진수 형태로 반환하는데 이 메소드가 하는 역할 입니다.

toBinaryString(int num) 은 숫자를 입력값을 받아서 그것을 진수로 바꿔서 이것을 String 타입으로 반환하는 겁니다.

그러니까 위 문제에서 요구한 두개의 스트링 입력값을 받아서 그것을 더한 후 그 이진수를 스프링으로 반환하는 것은 이 한 줄이면서 간단하게 해결 됩니다.

    return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));

Integer.parseInt(a,2)는 입력받은 이진수 a를 10진수로 바꿉니다.

Integer.parseInt(b.2)는 입력받은 이진수 b를 10진수로 바꿉니다.

그리고 이 두 값을 더한 후 toBinaryString()이 다시 이진수로 만들고 이것을 String 타입으로 변환해서 반환합니다.

그러면 이 문제에 대한 해답이 될 수 있습니다. 그런데 여기에서 문제가 있습니다.

이렇게 하면 자릿수가 많은 입력값은 NumberFormatException이 발생합니다.

String을 numeric type으로 변환하는데 있어서 적당한 포맷이 없기 때문에 일어나는 예외 입니다.

Integer, Long, BigInteger 등 모든 Numeric type은 자릿수 제한이 있기 때문입니다.

이 문제를 해결하기 위해서는 좀 더 복잡한 로직을 만들어야 합니다.

첫번째 방법은 bit 별로 계산하는 겁니다.

 이진수에서 1+1 은 10 이 됩니다.

1+0 = 1, 0+0 은 0이 되구요.

이렇게 그냥 비트 단위에서 계산하는 겁니다.

이것을 코딩하면 아래와 같이 됩니다.

class Solution {
  public String addBinary(String a, String b) {
    int n = a.length(), m = b.length();
    if (n < m) return addBinary(b, a);
    int L = Math.max(n, m);

    StringBuilder sb = new StringBuilder();
    int carry = 0, j = m - 1;
    for(int i = L - 1; i > -1; --i) {
      if (a.charAt(i) == '1') ++carry;
      if (j > -1 && b.charAt(j--) == '1') ++carry;

      if (carry % 2 == 1) sb.append('1');
      else sb.append('0');

      carry /= 2;
    }
    if (carry == 1) sb.append('1');
    sb.reverse();

    return sb.toString();
  }
}

입력 받은 두 값 중 자릿수가 큰 입력값의 크기 만큼 for 문을 돌립니다.

For 문 안에는 이진수 계산법을 하는 로직을 있습니다.

이렇게 비트 단위로 계산 한 후 결과 값을 리턴 하는 방법이 첫번째 방법입니다.

두번째 방법은 XOR로 처리한 후 carry하는 방법입니다.

알고리즘은 아래와 같습니다.

스크립트는 아래와 같습니다.

import java.math.BigInteger;
class Solution {
  public String addBinary(String a, String b) {
    BigInteger x = new BigInteger(a, 2);
    BigInteger y = new BigInteger(b, 2);
    BigInteger zero = new BigInteger("0", 2);
    BigInteger carry, answer;
    while (y.compareTo(zero) != 0) {
      answer = x.xor(y);
      carry = x.and(y).shiftLeft(1);
      x = answer;
      y = carry;
    }
    return x.toString(2);
  }
}

참고로 이것을 Python으로 하면 아래와 같습니다.

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]

첫번째 방법과 두번째 방법의 Runtime과 Memory 차이는 이렇습니다.

솔직히 저로서는 두번째 방법은 자세하게 이해하기는 힘드네요.

그냥 이렇게 있구나 하는 정도로 이해하고 넘어 가기로 했습니다.

이번 문제는 한자리 숫자들로 이루어진 배열을 입력받아서 처리하는 겁니다.

그 숫자들로 구성된 한 숫자에 1을 더하는 겁니다.

즉 [1,2,3] 이면 123으로 생각해서 여기에 1을 더한 124를 한자리 숫자들로 이뤄진 배열인 [1,2,4] 로 만들어 반환하면 됩니다.

여기에는 세가지 경우의 수가 있습니다.

위와 같이 배열의 마지막 숫자가 9가 아니면 단순히 그 숫자에 1을 더하면 됩니다.

그런데 마지막 숫자가 9인 경우는 조금 다르게 접근 해야 합니다.

[1,2,9] 인 경우는 129가 되고 여기에 1을 더하면 130이 됩니다. 그러면 리턴값은 [1,3,0] 이 됩니다.

이 경우는 9인 값은 0이 되고 그 이전 값 중 9가 아닌 숫자에 1을 더하면 됩니다.

[8,9,9] 인 경우는 899가 되서 900으로 계산 되고 리턴값은 [9,0,0] 이 되겠죠.

한가지 경우가 더 있습니다.

모든 숫자들이 9인 경우입니다.

[9,9,9] 인 경우는 999 + 1 이 되서 1000이란 값이 계산 됩니다. 그럼 리턴 값은 [1,0,0,0] 이 됩니다.

모든 9는 0으로 되고 아이템을 하나 더 만들어서 그 값은 1로 해야 됩니다.

다음 3가지 조건을 만족하는 로직을 만들어야 합니다.

1. 맨 마지막 숫자가 9가 아닌 경우 : 마지막 숫자에 1을 더함

2. 마지막 숫자가 9 이 고 이전의 숫자 중 9가 아닌 숫자가 있는 경우 : 9를 0으로 바꾸고 9가 아닌 숫자에 1을 더하고 마친다.

3. 모든 숫자가 9인 경우 : 모든숫자를 0으로 바꾸고 맨 앞에 1을 하나 붙인다. (배열 크기가 하나 더 큰 새로운 배열을 만들어야 한다.

내가 만든 로직은 아래와 같습니다.

class Solution {
    public int[] plusOne(int[] digits) {
        
        int inputLeng = digits.length;
        
        if(digits[inputLeng-1] == 9) { // if last number is 9
            boolean allNine = true;
            for(int i=0; i < inputLeng - 1; i++) { // check if all numbers are 9
                if(digits[i] != 9) {
                    allNine = false;
                } 
            }
            if(allNine) { // if all 9s
                int[] newDigits = new int[inputLeng + 1]; // create new array (length is input + 1)
                newDigits[0] = 1; // first one is 1
                for(int n=1; n < inputLeng-1; n++) { // all others are 0
                    newDigits[n] = 0;
                }
                return newDigits;
            } else { // if at least one number is not 9
                for(int j=inputLeng-1; j >= 0; j--) {
                    if(digits[j] != 9) {
                        digits[j] = digits[j] + 1; // not 9 + 1
                        break; // escape for loop
                    }
                    digits[j] = 0; // not 9 should be 0
                }
            }
        } else { // if last number is not 9 then just +1
            int plusOne = digits[inputLeng-1] + 1;
            digits[inputLeng-1] = plusOne;
        }
        return digits;
    }
}

이것을 조금 더 간단하게 리팩토링 해서 만든 것이 아래 로직 입니다.

class Solution {
  public int[] plusOne(int[] digits) {
    int n = digits.length;

    // move along the input array starting from the end
    for (int idx = n - 1; idx >= 0; --idx) {
      // set all the nines at the end of array to zeros
      if (digits[idx] == 9) {
        digits[idx] = 0;
      }
      // here we have the rightmost not-nine
      else {
        // increase this rightmost not-nine by 1
        digits[idx]++;
        // and the job is done
        return digits;
      }
    }
    // we're here because all the digits are nines
    digits = new int[n + 1];
    digits[0] = 1;
    return digits;
  }
}

이 로직은 하나의 for 을 사용했는데요. 그 안에서 아래와 같은 일을 합니다.

- 일단 모든 9을 0으로 바꾼다. 0이 아닌 값이 있으면 1을 더해서 리턴한다.

이렇게 되면 위 경우의 수 1번과 2번이 해결 됩니다.

모든 숫자가 9인 경우는 for 문 안에 있는 else 가 실행되지 않고 그 아래 코드로 넘어 가는데요.

여기서 배열의 크기를 하나 늘린 새로운 배열을 만들어서 맨 앞에 1을 넣습니다.

아래 3개가 첫번째 로직 으로 돌린 것이고 위에 3개가 두번째 로직을 돌린 겁니다.

For 루프를 하나밖에 안 쓴 두번째 로직 이 훨씬 빠릅니다.