[Leetcode] 67. Add Binary

Identifying the Problem

두 이진수 문자열을 더해 이진수 문자열을 return 한다.

Organizing thoughts

1. 일단 a 가 긴지, b가 긴지 몰라서 a를 긴 문자열로 정했다.

2. 자리수가 증가할 수 있으므로 a의 길이 + null 문자열 + 1 만큼 동적할당하였다.

3. a와 b의 상태를 파악하고 둘 더한 값을 stack 에 채워 넣는다.

3-1 stack은 채워지는 값을 뜻 하고, flag는 넘기는 수를 뜻 한다. 

a b 합이 1인 경우 flag을 올려 더 큰 자리수에 1을 넘겨 준다.

4. 이거를 표로 정리하면 다음과 같다.

a	b	flag	sum
0	0	0	0
0	0	1	1
0	1	0	1
1	0	0	1
0	1	1	2
1	0	1	2
1	1	0	2
1	1	1	3

5. sum 이 2이면 flag를 세우고, stack에 0을 채운다.

   sum 이 3이면 flag를 세우고, stack에 1을 채운다.

   0과 1 인경우는 stack에 0또는 1을 채운다.

 

6. sum는 매 시도마다 초기화 한다. 

7. 만들어진 stack을 뒤집는다. (이유는 가장 작은 자리수가 가장 큰 자리수가 되었기 때문이다)

Sourcecode

#include <string.h>
#include <stdlib.h>

char * addBinary(char * a, char * b){
    int a_l = strlen(a);
    int b_l = strlen(b);
    char * c;
    int flag = 0;
    int sum = 0;
    
    
    if(b_l>a_l) //1
    { 
        c = a;
        a = b;
        b = c;
        
        a_l = strlen(a);
        b_l = strlen(b);
        
    }
    
    char* stack = malloc(sizeof(char) * a_l + 2) ; //2
    
    *stack = 0;
    
    
    
    for(int i=0; i<a_l; i++)
    {
     if(a[a_l-1- i] == '1') sum += 1; //3
     if (flag ==1) sum += 1;
        
     if(i<b_l)
        if(b[b_l-1- i]=='1') sum += 1; 
     

      if(sum == 0)                     //5
      {  strcat(stack,"0"); flag = 0;}
        
      else if(sum == 1)
      {  strcat(stack,"1"); flag = 0;}
         
      else if(sum == 2)
      {  strcat(stack,"0"); flag = 1;}
         
      else if(sum == 3 )
      {  strcat(stack,"1"); flag = 1;}
    
        sum = 0; //6
     }
    
     if(flag == 1) 
         strcat(stack,"1");

    int len = strlen(stack) - 1;
          
    

   char tmp;
    
   for(int i=0;i<=len/2;i++)
   {
      tmp = *(stack+len-i);
      *(stack+len-i) = *(stack+i);
      *(stack+i) = tmp;
    
   }
 

   return stack;

}