2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

 

Add Two Numbers - LeetCode

두 연결 리스트의 각 노드 숫자를 합하여, 새 노드를 만들어 리턴하는 문제. 해결하는데 생각보다 시간이 많이 걸렸다.

---

 

문제 해결 6단계

 

1. 문제를 읽고 이해한다. 

 

=> You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

=> 숫자가 역순으로 저장된 두 연결리스트가 주어지고, 이 각각의 숫자들을 더한 합을 연결리스트로 구현. 두 연결리스트의 숫자는 그 자체가 0인 경우를 제외하고, 0으로 시작되지는 않음.

Constraints:

• The number of nodes in each linked list is in the range [1, 100]. => 이 부분에서 첫 에러가 등장... 역시 제한사항을 잘 읽어야함.
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 

---

2. 문제를 익숙한 용어로 재정의한다. 

=> 각각의 연결 리스트를 쭉 순회하면서 모은 숫자들 두개 합 -> 새로운 숫자 탄생. 이 새로운 숫자를 새로운 연결리스트에 똑같이 역순 저장.

 

---

3. 어떻게 해결할지 계획을 세운다. 

=> 첫 접근은 문제의 제시 내용과 똑같이, 각 노드들을 순회하면서 숫자를 합했음. 그리고 그 숫자를 새로운 연결리스트에다 역순으로 저장했음. 그러다보니 연결 리스트 노드 갯수가 최대 제한사항인  100개일 시, 100자리 이상의 정수가 필요했고, 이는 정수 자료형에 담기 힘듬.

=> 두번째 접근은 어차피 역순으로 저장될 것이므로, 두 연결리스트의 각 노드 합을 새로운 노드에 부여하는 형식으로 접근(해결 전략 8.순서 뒤집기).

 

---

4. 계획을 검증한다. 

 

=> 두 연결리스트 길이가 동일할 시-> 문제 없음. 두 연결리스트 길이가 다를 시 -> 문제 없음. 주어진 연결리스트 길이가 0이거나 100일 시 -> 문제없음. 

 

---

5. 프로그램으로 구현한다. 

=> 가장 발목을 잡았던 부분은 숫자를 올림하는 경우. previous node를 만들어서 이전 노드의 합이 10이상일 시 올림하는 방법도 생각해봤는데, 코드가 너무 꼬임. 결국 해답은 carry 변수를 생성 후 carry = (연결 리스트1의 노드.val + 연결리스트2의 노드.val + carry) % 10 을 해주는 거였음.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        int carry = 0;
        ListNode *p1 = l1, *p2 = l2, *cur = NULL, *head = NULL;
        
        
        while (p1 != NULL and p2 != NULL) {
            
            int val = (p1->val + p2->val + carry) % 10;
            carry = (p1->val + p2->val + carry) / 10;
            
            ListNode *newNode = new ListNode(val);
            if (head == NULL) 
                head = newNode;
            else 
                cur->next = newNode;                
                
            prev = cur;
            cur = newNode;
            p1 = p1->next;
            p2 = p2->next;
                
        };
        
        while (p1 != NULL) {
            int val = (p1->val + carry) % 10;
            carry = (p1->val + carry) / 10;
            
            p1->val = val;
            cur->next = p1;
            cur = p1;
            p1 = p1->next;
        };
                
        while (p2 != NULL) {
            int val = (p2->val + carry) % 10;
            carry = (p2->val + carry) / 10;
            
            p2->val = val;
            cur->next = p2;
            cur = p2;
            p2 = p2->next;
        };          

        if (carry != 0) {
            ListNode *newNode = new ListNode(carry);
            cur->next = newNode;
        }
            
        return head;
    }
};

 

 

---

6. 어떻게 풀었는지 되돌아보고, 개선할 방법이 있는지 찾아본다.

 

 

 

정답 코드:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

=> 내 코드에선 중복되는 코드가 너무 많다. 삼항 연산자로 p1이나 p2가 NULL인 경우에도 while문 안에서 처리가 가능했구나.

=> 더미 노드를 지정하고, 더미 노드의 next를 반환하는 방법이 참신했다. 헤드 노드인지 검사하는 if문을 넣을 필요가 없었네.

=> 중복되는 코드를 줄여 나가자.