LeetCode 67번 - Add Binary

문제 살펴보기

이진수 형태의 문자열이 2개 주어진다. 두 이진수 문자열을 이진수 계산법을 합산한 후, 그 결과를 반환하는 문제이다.

 

---

생각의 흐름

처음에는 주어진 두 문자열을 십진수로 바꿔서 더하고, 그 값을 다시 이진수로 만들어 반환하려고 했다. 

 

하지만 이 방법은 주어진 문자열이 아주아주아주 길면 사용할 수 없다.

 

문자열, 즉 String 객체는 JVM의 heap 메모리가 허용하는 만큼 길어질 수 있지만

int 자료형은 -2^32 ~ (2^32)-1 까지,

long 자료형은 -2^64 ~ (2^64)-1 까지만 가능하다.

 

그래서 아주 긴 문자열이 주어지면 오버플로우가 발생한다..

 

문제에서도 위 방법을 사용해 제출하면 중간에 걸리게 된다(testcase 중에 아주 긴 문자열이 주어지는 케이스가 있다).

 

그래서 문자열의 뒤쪽부터 직접 더하는 방법으로 풀었다.

 

---

풀어보기1

방법은 다음과 같다.

 

1. 두 문자열의 길이에서 1을 뺸 값을 각각 int형 변수 i, j 에 대입했다. 두 변수는 인덱스 번호로 사용하려고 한다.

2. 자리올림 숫자를 저장할 변수 carry를 선언하고 0으로 초기화했다.

3. 합산결과를 저장할 문자열 binary를 준비한다. 

 

4. 반복문을 이용해 주어진 두 문자열의 끝 부분 숫자부터 이진수 계산을 시작한다.

4-1. 합산한 값을 저장할 변수 sum을 선언하고, carry로 초기화한다.

4-2. 주어진 두 문자열에서 문자를 하나씩 꺼내 int 자료형으로 바꾼 후, sum에 더한다.

 

4-3. 준비한 문자열 binary의 앞에, sum을 2로 나눈 나머지를 더한다.

예를 들어 sum이 1일 경우 binary에 "1"이 추가되고, sum이 2일 경우에는 binary에 "0"이 추가된다.

 

4-4. sum을 2로 나눈 후, 몫을 carry에 저장한다.

예를 들어 sum이 1일 경우 carry는 0이 되고, sum이 2일 경우에는 carry가 1이 된다.

 

5. 반복문이 끝나면, carry가 1인지 확인한다. 만약 carry가 1이면, 자리올림이 반영해야 하므로 문자열의 앞에 "1"을 추가한다.

 

작성한 전문은 다음과 같다.

int i = a.length() -1;
int j = b.length() -1;
int carry = 0;

String binary = "";

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

if(carry==1) binary = 1 + binary;

return binary

제출은 잘 되었지만... 속도와 메모리 사용량 등 성능이 매우 나빴다.

 

저성능의 원인은 String 객체에 있다.

 

String 객체는 참조형이며, 불변 속성을 가지고 있다. 

 

그래서 String 객체에 +를 이용해 새로운 문자를 더해도 기존 String 객체의 값 자체가 바뀌지 않는다

대신 새로운 String 객체가 메모리에 할당된 후, 새 객체를 참조하게 된다.

 

이 때, 기존 String 객체는 사용되지 않는 상태로 메모리에 남는다..

 

이러한 이유로 String 객체의 연산은 메모리를 많이 사용하고, 속도도 느리다.

 

 

그래서 문자열을 자주 수정해야 하는 경우, StringBuilder를 사용하는 것이 좋다고 한다.

 

StringBuilder는 문자열을 만들 수 있는 클래스인데, String과 달리 가변 속성을 가지고 있어 연산에 적합하다고 한다.

 

(StringBuilder와 비슷한 클래스로 StringBuffer가 있다. StringBuilder와 비슷한 기능을 하는데 동기화 여부에 차이가 있다고 한다. 공부한 후 다시 정리하려고 한다.)

 

StringBuilder에는 여러 메서드가 있지만, 지금 필요한 메서드는 딱 2개이다.

 

- .append(추가할 값) : StringBuilder의 문자열의 맨 뒤에 '추가할 값'을 더한다.  

- .reverse() : StringBuilder의 문자열을 뒤집는다.

---

풀어보기2

StringBuilder를 이용해서 문제를 다시 풀어보았다.

 

원리는 풀어보기1과 같고

마지막에 toString() 메서드를 이용해 StringBuilder 클래스로 만든 문자열을 String 자료형으로 변환해주었다.

 

int i = a.length() -1;
int j = b.length() -1;
int carry = 0;

StringBuilder stringBuilder = new StringBuilder();

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

if(carry==1) stringBuilder.append(1);

return stringBuilder.reverse().toString();

 

풀어보기1의 방법을 사용 시 성능이 Runtime 8ms, Memory 42.4MB였는데 

StringBuilder를 사용했을 때에는 Runtime 1ms, Memory 40.7MB로 크게 개선되었다..