LeetCode 2. Add Two Numbers [Java]

문제

Add Two Numbers - LeetCode

ListNode로 정의된 두 수의 합을 구해 ListNode를 반환해야 한다. 처음 봤을 때는 입력과 출력이 배열 형태처럼 표기되어 있어 헷갈렸는데, 연결 리스트의 루트 노드를 파라미터로 받거나 반환하면 된다.

1차 풀이 (Runtime Error)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> deque1 = new ArrayDeque<>();
        Deque<Integer> deque2 = new ArrayDeque<>();

        ListNode cur = l1;
        while (true) {
            deque1.addFirst(cur.val);
            if (cur.next == null) break;
            cur = cur.next;
        }

        cur = l2;
        while (true) {
            deque2.addFirst(cur.val);
            if (cur.next == null) break;
            cur = cur.next;
        }

        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        while (!deque1.isEmpty()) {
            sb1.append(deque1.pollFirst());
        }
        while (!deque2.isEmpty()) {
            sb2.append(deque2.pollFirst());
        }

        long n1 = Long.parseLong(sb1.toString());
        long n2 = Long.parseLong(sb2.toString());
        String sum = Long.toString(n1 + n2);
        
        cur = null;
        ListNode prev = null;
        for (int i = 0; i < sum.length(); i++) {
            cur = new ListNode(sum.charAt(i) - '0', prev);
            prev = cur; 
        }

        return cur;
    }
}

대부분의 테스트 케이스를 통과했지만, 세상에 Medium 레벨에서 long의 범위를 넘어서는 숫자까지 테스트 케이스로 낼 줄은 꿈에도 몰랐다.

2차 풀이 (10ms)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

import java.util.Deque;
import java.util.ArrayDeque;
import java.math.BigInteger;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> deque1 = new ArrayDeque<>();
        Deque<Integer> deque2 = new ArrayDeque<>();

        ListNode cur = l1;
        while (true) {
            deque1.addFirst(cur.val);
            if (cur.next == null) break;
            cur = cur.next;
        }

        cur = l2;
        while (true) {
            deque2.addFirst(cur.val);
            if (cur.next == null) break;
            cur = cur.next;
        }

        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        while (!deque1.isEmpty()) {
            sb1.append(deque1.pollFirst());
        }
        while (!deque2.isEmpty()) {
            sb2.append(deque2.pollFirst());
        }

        /* ▼ 이 부분 수정 */
        BigInteger n1 = new BigInteger(sb1.toString());
        BigInteger n2 = new BigInteger(sb2.toString());
        String sum = n1.add(n2).toString();
        /* ▲ 이 부분 수정 */
        
        cur = null;
        ListNode prev = null;
        for (int i = 0; i < sum.length(); i++) {
            cur = new ListNode(sum.charAt(i) - '0', prev);
            prev = cur; 
        }

        return cur;
    }
}

long 대신 숫자 크기 제한이 없는 BigInteger를 사용했다. Accepted 자체는 되었지만 런타임 시간 분포를 보니 최적의 코드는 아닌 듯한 모양이다.

3차 풀이 (1ms)

2차 코드는 다음과 같은 과정을 거쳤다.

• 2 → 4 → 3을 큐/스택에 넣어 342로 복원
• BigInteger로 변환 후 덧셈 실행
• 결과를 다시 문자열로 바꿔 한 글자씩 연결 리스트로 다시 생성

이 방식은 숫자로 다 합쳤다가 다시 쪼개는 과정에서 메모리와 실행 시간이 매우 많이 소요되었다. BigInteger와 StringBuilder 객체도 매번 생성하며 메모리도 많이 소요했다.

 

잠시 초등학생 시절로 돌아가서 두 수의 덧셈을 했던 방법을 떠올려보자.

덧셈이 1의 자리에서부터 역순으로 시작하는 것을 볼 수 있다. 여기에 올림수(carry)가 생기면 그것까지 더해줘야 한다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cur = root;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry != 0) {
            cur.next = new ListNode(1);
        }

        return root.next;
    }
}