[JavaScript] Lv0 - 두 수의 합

두 수의 합

문제 설명

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

---

제한사항

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

---

입출력 예

a	b	result
"582"	"734"	"1316"
"18446744073709551615"	"287346502836570928366"	"305793246910280479981"
"0"	"0"	"0"

---

입출력 예 설명

입출력 예 #1

• 예제 1번의 a, b는 각각 582, 734이고 582 + 734 = 1316입니다. 따라서 "1316"을 return 합니다.

입출력 예 #2

• 예제 2번의 a, b는 각각 18446744073709551615, 287346502836570928366이고 18446744073709551615 + 287346502836570928366 = 305793246910280479981입니다. 따라서 "305793246910280479981"을 return 합니다.

입출력 예 #3

• 예제 3번의 a, b는 각각 0, 0이고 0 + 0 = 0입니다. 따라서 "0"을 return 합니다.

---

문제의 핵심은 일반 정수 타입으로 표현할 수 없을 만큼 큰 숫자를 문자열 형태로 받아 직접 덧셈 로직을 구현하는 것이다.

JavaScript의 Number 혹은 BigInt를 쓸 수도 있지만, 이 문제는 문자열 기반 덧셈 알고리즘을 직접 구현하는 경험을 요구한다.

---

1. 문제의 본질: 문자열 기반 수학 연산

일반 덧셈은 다음의 규칙을 따른다.

1. 가장 낮은 자리부터(오른쪽부터) 계산한다.
2. 각 자리수의 합이 10 이상이면 올림(carry) 를 발생시킨다.
3. 모든 자리를 순회한 뒤 마지막에 carry가 남는다면 가장 앞에 추가한다.

문자열 덧셈도 동일한 원리에 기반하지만, 차이가 있다.

• 숫자를 배열로 변환하거나 거꾸로 순회해야 한다.
• 한 문자열의 길이가 더 길 수 있으므로 두 포인터 방식이 유용하다.
• 반복 횟수는 max(a.length, b.length)으로 결정되며, 최대 100,000번이므로 O(N) 단일 패스로 충분히 빠르다.

---

2. 기본 알고리즘: Two-Pointer + Carry

핵심 의사코드

• i = a.length - 1, j = b.length - 1
• carry = 0
• while i ≥ 0 or j ≥ 0 or carry > 0
  • 각 자리 숫자를 더함
  • carry 업데이트
  • 문자열에 결과 누적
• 문자열 뒤집기

이 구조는 단일 패스 + 상수 공간의 carry 관리라는 측면에서 가장 이상적이다.

---

3. JavaScript 구현 — 최적화 버전

function solution(a, b) {
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;
  const result = [];

  while (i >= 0 || j >= 0 || carry > 0) {
    const x = i >= 0 ? a.charCodeAt(i) - 48 : 0;
    const y = j >= 0 ? b.charCodeAt(j) - 48 : 0;

    const sum = x + y + carry;
    result.push(sum % 10);
    carry = Math.floor(sum / 10);

    i--;
    j--;
  }

  return result.reverse().join('');
}

구현 포인트

• charCodeAt 기반 숫자 변환은 문자열 → 숫자 변환 중 가장 빠른 방법 중 하나이다.
• 결과를 배열에 push한 뒤 마지막에 reverse()하는 방식이 가장 단순하며 성능도 충분히 좋다.
• 매 반복에서 정수 연산만 수행되므로 O(N) 시간에 안정적으로 동작한다.

---

4. 대안적 접근법 비교

4.1 BigInt 사용 (간단하지만 비권장)

function solution(a, b) {
  return (BigInt(a) + BigInt(b)).toString();
}

장점

• 가장 간단하다.
• 자바스크립트 내장 기능을 활용해 읽기 쉽다.

단점

• 문제 취지와 다르다.
• 메모리 사용량 증가, 초대형 입력(10⁵ 자리의 문자열)을 BigInt로 변환하는 비용이 매우 크다.
• 일부 플랫폼에서는 BigInt 연산 overflow나 성능 문제가 발생할 수 있다.

실무에서는 BigInt로 처리하는 것이 이득인 경우도 많지만, 알고리즘 문제에서는 직접 구현이 정답이다.

---

4.2 앞에서부터 누적하는 방식 (비효율)

// 비효율적: 문자열 앞에 추가 → 매 삽입마다 O(n)
result = digit + result;

이 방식은 문자열 concat 비용이 누적되어 O(N²) 로 악화될 수 있으므로 금지해야 한다.

---

5. 학습 포인트 정리

문자열 기반 수학을 구현할 때 반드시 고려해야 하는 요소

• 자리수 순회는 오른쪽부터
• 하위 단계에서 발생하는 carry는 상위 단계로 전파
• 문자열 덧셈은 결국 배열 + reverse() 로 귀결된다
• JavaScript에서 숫자 변환은 charCodeAt이 빠르다
• 두 포인터 방식은 큰 입력에서도 성능을 보장한다