두 개의 이진 문자열 a와 b가 주어졌을 때, 이 두 이진수를 더한 합계를 구하고 그 결과 역시 문자열 형태로 반환해야 합니다.
예를 들어 입력이 a = "10110", b = "10010"이라면, 출력은 "101000"이 됩니다.
문제 해결 접근 방법
이 문제는 우리가 손으로 이진수 덧셈을 하는 방식과 동일하게 풀 수 있습니다. 뒷자리부터 한 자리씩 더하면서 올림수(carry)를 관리하면 됩니다. 구체적인 단계는 다음과 같습니다.
- 결과를 저장할 빈 문자열 ret을 준비합니다.
- na := a의 길이, nb := b의 길이로 설정합니다.
- i := na - 1, j := nb - 1로 초기화하여 각 문자열의 마지막 인덱스를 가리킵니다.
- carry := 0으로 올림수를 초기화합니다.
- i >= 0 또는 j >= 0인 동안 다음을 반복합니다:
- addA := i >= 0이면 a[i]에서 '0'의 ASCII 값을 뺀 숫자, 아니면 0
- addB := j >= 0이면 b[j]에서 '0'의 ASCII 값을 뺀 숫자, 아니면 0
- sum := addA + addB + carry
- carry := sum / 2 (새로운 올림수 계산)
- sum := sum mod 2 (현재 자리의 값)
- ret := ret에 sum을 이어 붙입니다.
- i를 1 감소시키고, j도 1 감소시킵니다.
- 반복 종료 후 carry가 0이 아니라면 ret에 carry를 이어 붙입니다.
- ret을 뒤집습니다. (뒷자리부터 계산했기 때문)
- ret을 반환합니다.
두 문자열의 길이가 다를 수 있으므로, 짧은 쪽은 범위를 벗어난 경우 0으로 처리한다는 점이 핵심입니다. 또한 마지막에 올림수가 남아 있으면 결과 맨 앞에 추가해야 한다는 것도 잊지 말아야 합니다.
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string solve(string a, string b){
string ret = "";
int na = a.size();
int nb = b.size();
int i = na - 1;
int j = nb - 1;
int carry = 0;
while(i >= 0 || j >= 0){
int addA = i >= 0 ? a[i] - '0' : 0;
int addB = j >= 0 ? b[j] - '0' : 0;
int sum = addA + addB + carry;
carry = sum / 2;
sum %= 2;
ret += to_string(sum);
i--;
j--;
}
if(carry)
ret += to_string(carry); reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
string a = "10110", b = "10010"; Solution ob;
cout << ob.solve(a, b);
}입력
"10110","10010"
출력
101000
복잡도 분석
이 알고리즘은 두 문자열 중 더 긴 쪽의 길이를 n이라 할 때 시간 복잡도 O(n), 공간 복잡도 역시 결과 문자열 저장을 위해 O(n)입니다. 문자열을 직접 정수로 변환하지 않기 때문에 매우 큰 이진수도 오버플로우 없이 처리할 수 있다는 장점이 있습니다.