리트코드 - 67. Add Binary

리트코드 - 67. Add Binary

출처 - https://leetcode.com/problems/add-binary/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

두 개의 이진 문자열 a와 b가 주어지면 그 합을 이진 문자열로 반환합니다.

 

의사코드

i = a.length() - 1 j = b.length() - 1 carry = 0 sb = new StringBuilder 반복문 시작 (i >=0 또는 j >= 0 또는 carry > 0)     if (i >= 0)         carry += a.charAt(i) - '0';     if (j >= 0)         carry += b.charAt(j) - '0';     sb.append(carry % 2)     carry /= 2     i--     j-- 반복문 종료 sb.reverse.toString() 리턴

 

풀이코드

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

        while (i >= 0 || j >= 0 || carry > 0) {
            if (i >= 0) {
                carry += a.charAt(i) - '0';
            }
            if (j >= 0) {
                carry += b.charAt(j) - '0';
            }

            sb.append(carry % 2);
            carry /= 2;
            i--;
            j--;
        }

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

코드설명

이진수를 더하는 연산이다.

간단하게 생각하면 이진수를 십진수로 변환해서 더한다음 다시 십진수를 이진수로 더하면 된다.

 

그렇지만 두가지를 고려해봐야 한다.

1) 변환한 십진수의 합이 int형의 크기를 벗어나는 경우

2) 2진수에서 10진수로 변환하는 것이 필요한 연산인가

 

이 두가지를 고려했을 때 이진수는 이진수로서 더해야 한다.

 

따라서 주어진 String에서 각 끝자리부터 더하여 올림이 있거나 남은 자리가 있을때까지 반복문을 돌린다.

올림에는 carry 변수를 이용해서 더해주도록 한다.

 

이렇게 연산한 결과를 stringbuilder로 append 해주면 정확히 반대로 값이 적히게 되는데 reverse 를 이용하여 반대로 출력하면 원하는 값을 얻을 수 있다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

(n은 가장 긴 문자열의 길이)

 

문제를 풀며 생각한 흐름과 배운 점

처음에는 배열을 담아서 해결할까 생각이 들다보니 문자열을 자르는 방법을 선택했다.

문자열을 다루는 문제에서는 대게 문자열 자체로 해결해야지 배열을 사용하는 경우 메모리를 많이 먹었기 때문이다.

그래서 substring을 이용했다.

초기 코드

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

        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = 0;

            if (i >= 0) {
                sum += Integer.parseInt(a.substring(i, i + 1));
            }
            if (j >= 0) {
                sum += Integer.parseInt(b.substring(j, j + 1));
            }

            sum += carry;
            carry = sum / 2;
            sb.insert(0, sum % 2);
            i--;
            j--;
        }

        return sb.toString();
    }
}

물론 런타임은 3ms로 28%, 메모리는 13% 로 좋지 않은 편에 속했다.

원인으로 생각한것은

1. Integer.parseInt() 메소드

2.stringbuilder의 insert() 메소드

 

이다.

메소드를 들여다보니 String을 가져오면 부호를 판단하고, charAt()으로 값을 가져오고 있었다!

그래서 charAt()메소드도 들여다보니

역시나 charAt은 간단했다.

유니코드의 일부인 Latin-1 문자 집합이면 위의 메소드를, 아니면 UTF16을 사용하는 메소드를 호출하고 있었다.

charAt 을 사용하면 굳이 substring을 사용하지 않아도 되고, charAt으로 해결이 가능해진다.

 

리팩토링

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

        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = 0;

            if (i >= 0) {
                sum += a.charAt(i) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j) - '0';
            }

            sum += carry;
            carry = sum / 2;
            sb.insert(0, sum % 2);
            i--;
            j--;
        }

        return sb.toString();
    }

이를 토대로 위와 같이 줄이니 런타임이 2ms 56%, 메모리도 24%로 다소 올라갔다.

하지만 여전히 sb.insert가 거슬린다.

 

최종코드(= 풀이코드)

LinkedList에서 addFirst()같은 메소드를 사용할때 값을 밀어내는 것처럼 sb.insert() 메소드도 구현되어 있었기 때문에 다른 방식이 필요했다.

찾아보니 sb.reverse라는 메소드가 있어 이것을 활용하기로 했다.

 

그리고 sum 변수도 굳이 사용하지않고 carry로 더해주면 되므로 변수로 쓰이는 메모리가 하나 줄어들었다.

최종적으로 둘다 99% 에 가까운 코드를 만들었다.

 

정리

이진수 연산 방법

stringbuilder를 역으로 꺼내는 방법