[1주차] 2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-interview-150 

Add Two Numbers - LeetCode

---

📝 문제

두 개의 0 이상 9 이하의 정수가 저장된 LinkedList가 주어진다. 노드의 값은 전체 숫자의 역순으로 저장되어 있다.

예를 들어, 342 숫자는 List에 [2, 4, 3] 으로 저장된다.

두 LinkedList 에서 표현하는 수를 더한 결과를 새 LinkedList에 저장해 리턴하시오.

 

정의된 LinkedList

 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; }
 }

 

🎈 풀이

LinkedList 의 길이가 최대 100 이다. 즉, 최대 100자리의 정수를 나타내기 때문에 전체 수를 덧셈하기에는 수의 범위가 너무 크다. 따라서 각 자릿수를 각각 더한 후, 새로운 LinkedList 에 담아야 한다.

다행히 역순으로 저장되어 있기 때문에 l1[0] + l2[0], l1[1] + l2[1] ... 식으로 더해가며 저장하면 된다. 

단, 자리올림을 고려해야 한다.

 

시간복잡도: O(n)

공간복잡도: O(1)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int carry = 0;
    ListNode resultHead = null;
    ListNode currentNode = null;
    ListNode node1 = l1;
    ListNode node2 = l2;

    while (node1 != null || node2 != null) {
        int num1 = 0;
        int num2 = 0;
        if (node1 != null) num1 = node1.val;
        if (node2 != null) num2 = node2.val;

        int sum = num1 + num2 + carry;
        carry = sum / 10;

        ListNode tempNode = new ListNode(sum % 10);
        if (currentNode == null) {
            currentNode = tempNode;
            resultHead = currentNode;
        } else {
            currentNode.next = tempNode;
            currentNode = currentNode.next;
        }

        if (node1 != null) node1 = node1.next;
        if (node2 != null) node2 = node2.next;
    }
    if (carry != 0) currentNode.next = new ListNode(1);


    return resultHead;
}

• resultHead: 최종적으로 리턴할 LinkedList의 Head
• currentNode: 삽입중인 결과 LinkedList의 tail
• node1, node2: l1, l2 의 각각 탐색중인 현재 노드
• 8행: 주어진 두 LinkedList 의 길이가 다를 수 있으므로 while 은 둘 다 null이 될 때만 빠져나온다.
• 26, 27행: 다음 노드가 존재할 때만 탐색한다.
• 29행: 로직이후 carry가 남아있다면 1 노드를 추가로 삽입한다.

 

1

 

2

3

4

 

4321 + 765 = 5086 이므로 잘 삽입되었음을 확인가능하다.

 

📈 타 솔루션 참고

시간복잡도: O(n)

공간복잡도: O(1)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode tail = dummyHead;
    int carry = 0;

    while (l1 != null || l2 != null || carry != 0) {
        int digit1 = (l1 != null) ? l1.val : 0;
        int digit2 = (l2 != null) ? l2.val : 0;

        int sum = digit1 + digit2 + carry;
        int digit = sum % 10;
        carry = sum / 10;

        ListNode newNode = new ListNode(digit);
        tail.next = newNode;
        tail = tail.next;

        l1 = (l1 != null) ? l1.next : null;
        l2 = (l2 != null) ? l2.next : null;
    }

    ListNode result = dummyHead.next;
    dummyHead.next = null;
    return result;
}

기본적인 알고리즘은 동일하나 좀더 깔끔하다.

나는 l1, l2 의 주소를 잃어버리는 것이 꺼림찍해서 추가로 node1, node2 를 선언하였으나 어짜피 이후에 사용하지 않으므로 필요가 없는 변수이다. 그냥 l1, l2에서 탐색을 시작하면 된다.

또한 더미헤드를 사용하여 분기문의 수를 줄였다.

carry 조건도 while 조건에 넣어서 l1, l2가 둘다 null 이더라도 한번 더 실행하게 만들었다.