[LeetCode] Add Strings

415. Add Strings

문제

Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.

Example 1:
Input: num1 = "11", num2 = "123"
Output: "134"

Example 2:
Input: num1 = "456", num2 = "77"
Output: "533"

Example 3:
Input: num1 = "0", num2 = "0"
Output: "0"

Constraints:

• 1 <= num1.length, num2.length <= 10⁴
• num1 and num2 consist of only digits.
• num1 and num2 don't have any leading zeros except for the zero itself.

고민

String 을 Int 로 변환해서 더한 후 String 으로 반환하는 문제이다.
제약은, BigInteger를 사용하지 말것.그리고 string의 length 는 Int 또는 Long 으로 치환할 수 없는 크기의 length 가 들어온다.
그렇다면 해결 방식은, String 의 요소를 하나씩 Int 로 변경 후 더한 값을 String 으로 append 하는 방식이다.

내가 우선적으로 생각한 것은

1. String 의 요소를 거꾸로 탐색한다.
2. 올림(carry)를 어딘가 저장 후 그 다음 요소 덧셈시에 같이 덧셈한다.

생각은 해결 방안에 부합하지만, 이걸 어떻게 코드로 작성해야할지가 고민이 되었다.
일단 코드를 작성해보자.

해결

class Solution {
    fun addStrings(num1: String, num2: String): String {
        val numStr1 = num1.reversed()
        val numStr2 = num2.reversed()
        val forStr = if (numStr1.length > numStr2.length) numStr2 else numStr1
        val anotherForStr = if (numStr1.length > numStr2.length) numStr1 else numStr2
        val exceptionIndex = forStr.length
        val anotherNums = anotherForStr.substring(exceptionIndex)

        val result = StringBuilder()
        var carry = 0

        fun addDigit(d1: Char, d2: Char?, carryIn: Int): Int {
            val sum = d1.digitToInt() + (d2?.digitToInt() ?: 0) + carryIn
            result.append((sum % 10).toString())
            return sum / 10
        }

        // 공통 자리수 덧셈
        for (i in forStr.indices) {
            carry = addDigit(numStr1[i], numStr2.getOrNull(i), carry)
        }

        // 남은 긴 자리수 덧셈
        for (i in anotherNums.indices) {
            carry = addDigit(anotherNums[i], null, carry)
        }

        // 마지막 캐리 추가
        if (carry != 0) result.append(carry.toString())

        return result.reverse().toString()
    }
}

정말....... 푸는 것에만 집중한 코드다. 내부 함수로 덧셈을 구현하고, num1 과 num2 에서 공통된 index를 가진 요소를 계산하고 남은 요소들을 또 개산하기 위한 for문을 실행한다.
하지만.. 나로써는 이게 최선이었다........ (정말 많은 시행 착오가 있었다...ㅠ..)

결과

결과는 처참했다........ 나도 예상했다...... 어쨋든 결국 문제를 풀어야 다른 고수들의 코드를 볼 수 있으니... 하하핳하하하ㅏ....

후기

class Solution {
    fun addStrings(num1: String, num2: String): String {
        val sb = StringBuilder()
        var i = num1.length - 1
        var j = num2.length - 1
        var carry = 0

        while (i >= 0 || j >= 0 || carry != 0) {
            val digit1 = if (i >= 0) num1[i] - '0' else 0
            val digit2 = if (j >= 0) num2[j] - '0' else 0
            val sum = digit1 + digit2 + carry

            sb.append(sum % 10)
            carry = sum / 10

            i--
            j--
        }

        return sb.reverse().toString()
    }
}

너무 깔끔한 코드다. 항상 다른 사람들의 코드를 보면 "아 이렇게 풀 수 있었는데!!" 라고 하면서 왜 난 못하지.. 참.. 씁쓸하구만 ㅎㅎ
String 을 reversed할 필요가 없다. index만 있으면 되니까..
마찬가지로 거꾸로 확인할 수 있도록 반복 루프안에 감소식으로 index를 감소하였고, 루프의 조건은 모든 index가 0이 될때까지 돌면,
나처럼 남은 요소들 확인할 필요도 없다.
그리고 digitToInt()으로 변환할 필요도 없었다. 유니코드 코드로 확인할 수 있으니까.
또 하나 배우고, 기억해야할 것이 늘었다.