두 개의 이진 문자열과 b가 있다고 가정하고 이 이진수를 더하고 그 합을 문자열로 찾아야 합니다.
따라서 입력이 ="10110", b ="10010"과 같으면 출력은 "101000"이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ret :=빈 문자열
- na :=크기, nb :=b 크기
- i :=na - 1, j :=nb - 1
- 캐리:=0
- 동안(i>=0 또는 j>=0) 다음을 수행합니다.
- addA :=(i>=0이면 a[i] - '0'의 ASCII, 그렇지 않으면 0)
- addB :=(j>=0이면 b[j] - '0'의 ASCII, 그렇지 않으면 0)
- 합계 :=addA + addB + 캐리
- carry :=합계 / 2
- sum :=합계 모드 2
- ret :=ret 연결 합계
- (i 1 감소)
- (j를 1 감소)
- carry가 0이 아닌 경우:
- ret :=ret 연결 캐리
- ret 배열 반전
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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