Leet Code - 67. Add Binary(C++)

예제: Add Binary

문제
Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

풀이

이진수의 덧셈이다. 마냥 간단해 보이지만, 그렇지가 않았다.
물론 string index를 따라가며 계산하는것이 제일 접근성이 쉬워 보이지만, 필자는 10진수 변환 -> 두 수 더하기 -> 2진수 변환을 하고싶었다.

따라서 아래 코드와 같이 구현하였다.

class Solution {
public:
	string addBinary(string a, string b) {
		long long sum = 0;
		string res;

		int idx = 0;
		for (int i = a.size() - 1; i >= 0; i--) {
			sum += pow(2, idx) * (a[i] - '0');
			idx++;
		}

		idx = 0;
		for (int i = b.size() - 1; i >= 0; i--) {
			sum += pow(2, idx) * (b[i] - '0');
			idx++;
		}

		if (sum == 0) return "0";

		while (sum > 0) {
			res += to_string(sum % 2);
			sum /= 2;
		}

		reverse(res.begin(), res.end());
		return res;
	}
};

입력이 작으면 될 수도 있을 것이나, 위의 코드는 입력이 "1111111111111111111111111..........."와 같이 길어지면 자료형으로는 커버가 안 될 것이다. 그리고 굳이 반복문을 여러번 써서 좋지 못한 코드일 것이다. 그냥 해보고 싶었다(...)

각설하고, 필자가 푼 방법을 로직순으로 풀어 써 보면 아래와 같다.

1. a와 b의 길이를 비교하여 긴 문자를 a로, 짧은 문자를 b로 만든다.
2. a와 b를 reverse한다.(연산을 쉽게 하기 위해)
3. a와 b를 b의 길이까지 비교하며 이진수 덧셈을 하며, 연산의 결과는 a에 저장한다.
4. a에서 (b의 길이, a의 길이)를 살펴보며 2 이상이면 자릿수를 올려준다.
5. a를 reverse하여 return

다음은 전체적인 소스코드이다.

소스 코드

class Solution {
public:
	string addBinary(string a, string b) {
		if (a.size() < b.size()) {
			string tmp = a;
			a = b;
			b = tmp;
		}

		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());

		for (int i = 0; i < b.size(); i++) {
			int na = a[i] - '0';
			int nb = b[i] - '0';

			if (na + nb > 1) {
				a[i] = ('0' + na + nb - 2);
				if (i == a.size() - 1) a += "1";
				else a[i + 1]++;
			}
			else {
				a[i] = ('0' + na + nb);
			}
		}

		for (int i = b.size(); i < a.size(); i++) {
			if (a[i] == '2') {
				a[i] = '0';
				if (i == a.size() - 1) a += "1";
				else a[i + 1]++;
			}
			else break;
		}

		reverse(a.begin(), a.end());
		return a;
	}
};

풀이 후기

요즘 극심한 야근때문에 알고리즘 문제해결 전략을 전혀 못풀고 있다. 이러면 안되는데!!!!
그나마 leetcode의 easy 난이도를 풀고 있지만, 어째 점점 어려워지는 느낌이다.
easy 난이도가 끝나면 난항이 예상된다. 잘 헤쳐나가자!