알고리즘 문제풀이/LeetCode

LeetCode 67번 - Add Binary

 

leetcode.com/problems/add-binary/

 

Add Binary - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

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;
    }
};