leetcode 67, Add Binary

문제 설명

이진 수를 더하는 문제다. 간단하게 보일 수 있지만, 이진수를 어떻게 더하는지 모르면 제대로 못 푸는 문제다 그게 바로 나예요... 물론 지금은 알았다ㅎㅎ

이진 수란 0과 1로 이루어진 숫자로 둘이 더했을 때 2가 되면 1을 넘겨준다.

파랗게 표시된 부분이 1을 넘겨주는 부분이다. 그렇기에 1을 넘기는 것만 잘 이용한다면 문제 없이 풀 것이다 난 문제 있었음

코드 설명

1. a와 b중 길이가 더 긴 걸 문자열을 찾아준다. a가 더 긴 것으로 가정하고 b가 더 길다면 재귀함수를 이용해 a와 b의 순서를 바꿔준다.

2. 길이가 긴 걸로 반복문을 돌려주는데, 만일 반복문의 기준이 되는 문자열의 현재 문자가 1이라면 next에 1을 더해준다. 또한 상대 문자열이 범위에 있고 현재 문자가 1이라면 next에 1을 더해준다.

3. next를 2로 나눠서 나머지가 1이면 이는 next가 1이라는 의미이므로 1을 붙여준다. 나머지가 0이면 이는 두 문자가 1이거나 0이라는 의미이므로 0을 붙여준다.

4. 그리고 next를 2로 나눠주는데, 만일 next가 2라면 1이 나올 테니 1을 넘겨준다.

5. 반복문이 끝나고 next가 1이라 아직 계산이 남았다면 문자열에 1을 붙여준다.

6.문자열을 reverse() 함수로 거꾸로 돌려주고 반환하면 된다.

코드

import java.util.*;
import java.io.*;

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int lengthA = a.length();
        int lengthB = b.length();

        if(lengthA < lengthB){
            return addBinary(b, a);
        }

        int length = Math.max(lengthA, lengthB);
        int next = 0;
        int j = lengthB-1;

        for(int i=length-1; i>=0; i--){
            if(a.charAt(i) == '1'){
                ++next;
            }
            if(j > -1 && b.charAt(j--) == '1'){
                ++next;
            }

            if(next % 2 == 1){
                sb.append('1');
            }else{
                sb.append('0');
            }
            // next가 2가 되면 1을 넘겨준다.
            next /= 2;
        }

        if(next == 1){
            sb.append('1');
        }
        sb.reverse();

        return sb.toString();
    }
    
}

링크

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