Add Binary - LeetCode

Problem

1. input: 이진수 문자열 a, 이진수 문자열 b
2. output: a + b를 이진수로 표현한 문자열 리턴
   • 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.

Idea

한자리씩 분리하여 덧셈 후, 자릿수를 넘어가는 값 처리 → Sol1

Solution

1. 한자리씩 덧셈

   자릿수를 넘어가는 값 따로 저장하여 처리

   import java.lang.StringBuilder
   
   class Solution {
       fun addBinary(a_: String, b_: String): String {
           val sb = StringBuilder()
           // 1의 자리부터 비교를 위해 reverse
           val a = a_.reversed() 
           val b = b_.reversed()
           var idx = 0
           var pass = 0
           // 한자리씩 덧셈
           while (idx < maxOf(a.length, b.length)) {
               var value = 0
               if (idx < a.length) value += if (a[idx] == '1') 1 else 0
               if (idx < b.length) value += if (b[idx] == '1') 1 else 0
               value += pass
               pass = 0
               if (value >= 2) {
                   pass = 1
                   value -= 2
               }
               sb.append(value.toString())
               idx++
           }
           if (pass > 0) sb.append("1")
           return sb.reversed().toString()
       }
   }
   

   시간 복잡도: 문자열 순회

   

Point

1. 유사 문제: 1 더하기