[Java] 두 수의 합

문제

0 이상의 두 정수가 문자열 a, b로 주어질 때, a + b의 값을 문자열로 return 하는 solution 함수를 작성해 주세요.

 

 

제한사항

• 1 ≤ a 의 길이 ≤ 100,000
• 1 ≤ b 의 길이 ≤ 100,000
• a 와 b 는 숫자로만 이루어져 있습니다.
• a 와 b 는 정수 0이 아니라면 0으로 시작하지 않습니다.

 

import java.util.ArrayList;

class Solution {
    public String solution(String a, String b) {
        String answer = "";
        String shortNum = "", longNum = "";
        int aLen = a.length(), bLen = b.length();
        int over = 0;

        for(int i = 0; i < Math.abs(aLen - bLen); i++) {
            shortNum += "0";
        }
        shortNum += aLen < bLen ? a : b;
        longNum += aLen < bLen ? b : a;


        ArrayList<Integer> addNumList = new ArrayList<Integer>();
        for(int i = shortNum.length()-1; i >= 0; i--) {
            int num1 = shortNum.charAt(i) - '0';
            int num2 = longNum.charAt(i) - '0';
            addNumList.add((num1 + num2 + over) % 10);
            over = (num1 + num2 + over) / 10;
        }

        if(over != 0) {
            addNumList.add(over);
        }

        for(int i = addNumList.size()-1; i >= 0; i--) {
            answer += addNumList.get(i) + "";
        }

        return answer;
    }
}

 

이 문제는 단순히 주어지는 문자열을 숫자로 바꿔 해결하면 되지 않을까 했는데...

문자열의 길이가 최대 100,000인 것에 주목해야 한다.

문자열이 최대 100,000이라면 주어지는 정수가 자릿수가 최대 10만이란 소리이다.

int 자료형의 최대값을 보면, 2,147,483,647이다. 이정도 숫자만 해도 10자리밖에 되지 않는다.

그렇다면 더 큰 자료형인 long 타입을 보면... 9,223,372,036,854,775,807 이다. 즉, 19자리 이다.

그런데 주어지는 문자열의 길이, 즉, 정수의 최대 자릿수가 10만이라면... 단위가 몇이지...? 아무튼 댑빵 큰 값이란 소리다.

 

따라서 단순히 정수로 바꾼다고 해서 해결 될 문제가 아니다.(파이썬은 해주나?)

그래서 나는 주어지는 문자열을 하나씩 가져와서 연산을 했다. 뭐 int 자료형이 최대 10자리이니 9자리씩 끊어서 계산해도 될 것 같지만 9자리씩 끊어서 계산하다가 9자리 이하의 문자열이 남을경우 어떻게 해결할 것인지 머리가 생각하길 거부했다. 그래서 마음 편하게 한 자리씩 가져와서 10이 넘어가면 over 이란 변수에 넘어가는 10의 자리수를 저장해서 다음 연산에 포함했다. 우리가 흔히 덧셈을 하듯 말이다.

 

 

다른사람은 어떻게 해결했을까 다른분들의 코드도 확인해봤는데, 비슷한 생각을 했음에도 더욱 간단히 해결한 사람들이 있었다.

 

class Solution {
    public String solution(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;

        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;

            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 10);
            carry = sum / 10;
        }
        return sb.reverse().toString();
    }
}

아직 더 효율적으로 코드를 구현하기엔 좀 더 연습과 노하우가 필요한가보다.

 

 

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/181846