leetcode 67) Add Binary

LV. Easy 😎

https://leetcode.com/problems/add-binary/

Add Binary - LeetCode

 

문제

Given two binary strings a and b, return their sum as a binary string.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= a.length, b.length <= 10^4
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

 

문제 해결법

일단 a와 b의 길이가 10^4이면 10진수로 변환했을 때 max값은 2^10^4이다

unsigned longlong으로 해도 오버플로우가 날 것 같아서..

진수 변환을 굳이 하지 않고 string에서 계산을 해줬다!

2진수를 10진수로 바꾸고 다시 2진수로 바꾼 후 string으로 변환하는 게 시간도 더 오래 걸릴 거 같았음!

 

2진수의 첫 번째 자리부터 계산하는 것이 당연하기에!

a의 길이, b의 길이를 찾아 뒤에서부터 계산해서 새로운 string ans에 넣어줬다.

a의 길이와 b의 길이가 다를 수도 있으니깐 남은 a 또는 b의 문자열을 string ans에 넣어주면 계산 끝!

 

해결 코드

class Solution {
public:
	string addBinary(string a, string b) {
		int aLen = a.size();
		int bLen = b.size();
		int flag = 0;
		string ans = "";

		// a와 b 2*0자리부터 계산해주기
		while (aLen > 0 && bLen > 0) {
			aLen--;
			bLen--;
			flag += a[aLen] == '1' ? 1 : 0;
			flag += b[bLen] == '1' ? 1 : 0;
			ans = to_string(flag % 2) + ans;
			flag = flag / 2;
		}
		// a에서 남은 수 있으면 string에 넣어주기
		while (aLen > 0) {
			aLen--;
			flag += a[aLen] == '1' ? 1 : 0;
			ans = to_string(flag % 2) + ans;
			flag = flag / 2;
		}
		// b에서 남은 수 있으면 string에 넣어주기
		while (bLen > 0) {
			bLen--;
			flag += b[bLen] == '1' ? 1 : 0;
			ans = to_string(flag % 2) + ans;
			flag = flag / 2;
		}
		// 다음 자리로 올리는 수 있으면 string에 넣어주기
		ans = flag == 1 ? to_string(flag % 2) + ans : ans;
		return ans;
	}
};