leetcode.com/problems/add-binary/
class Solution {
// a와 b의 길이를 비교하여 긴 문자를 a로, 짧은 문자를 b로 만든다.
// a와 b를 reverse한다.(연산을 쉽게 하기 위해)
// a와 b를 b의 길이까지 비교하며 이진수 덧셈을 하며, 연산의 결과는 a에 저장한다.
// a에서 (b의 길이, a의 길이)를 살펴보며 2 이상이면 자릿수를 올려준다.
// a를 reverse하여 return
public:
string addBinary(string a, string b) {
string result = "";
//1) a와 b의 길이를 비교하여 긴 문자를 a로, 짧은 문자를 b로 만든다.
if(a.size()<b.size()){
string temp = a;
a = b;
b = temp;
}
//2)a와 b를 reverse한다.(연산을 쉽게 하기 위해)
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
//3)a와 b를 b의 길이까지 비교하며 이진수 덧셈을 하며, 연산의 결과는 a에 저장한다.
for(int i = 0; i<b.size(); i++){
//int형으로 만들어 주는 과정
int aa = a.at(i) - '0';
int bb = b.at(i) - '0';
if(aa+bb>1){
//다시 스트링으로 저장하기
a[i] = aa+bb-2+'0';
//두수의 길이가 같은 경우가 있을수도 있다.
//a.size()-1은 직관적이지 않아서 바꾸니까 더 빠르다.
if (a.size() == b.size() && i == b.size()-1){
a += "1";
}
//자리수 마지막이 아니면, a[i+1]을 1증가 시켜라, 즉 더라하
//아스키에서도 ++하면 다음 수로 넘어간다는 논리.
else{
a[i+1]++;
}
}
else{
a[i] = aa+bb+'0';
}
}
//4)a에서 (b의 길이, a의 길이)를 살펴보며 2 이상이면 자릿수를 올려준다.
for(int i = b.size(); i<a.size(); i++){
int aa = a.at(i) - '0';
if(aa>1){
a[i] = aa-2+'0';
//만약 a의 마지막 자리수 전이면, 맨뒤에 1을 붙여라!
if (i == a.size() - 1){
a += "1";
}
//자리수 마지막이 아니면, a[i+1]을 1증가 시켜라, 즉 더라하
//아스키에서도 ++하면 다음 수로 넘어간다는 논리.
else{
a[i+1]++;
}
}
}
//5)a를 reverse하여 return
reverse(a.begin(),a.end());
result = a;
return result;
}
};
'알고리즘 문제풀이 > LeetCode' 카테고리의 다른 글
LeetCode 13번 - Roman to Integer (0) | 2020.07.28 |
---|---|
LeetCode 686번- Repeated String Match (0) | 2020.07.28 |
LeetCode 14번 - Longest Common Prefix (0) | 2020.07.28 |
LeetCode 81번 - Search in Rotated Sorted Array II (0) | 2020.07.27 |
LeetCode 33번 - Search in Rotated Sorted Array (0) | 2020.07.27 |