[C++] LeetCode : Add Two Numbers

Question

두 개의 음이 아닌 integer type의 정수가 있는 linked list 가 주어질 때, 두 linked list의 합을 구하는 문제이다. linked list는 역순으로 저장되며, 답 또한 역순으로 출력해야 한다. 단, 주어진 list에서 0으로 시작하는 숫자는 없다고 가정한다. 즉, 숫자 003456과 같은 case는 없다. 

제약사항 

• 각 Linked List의 노드 개수는 [1,100] 이다.
• 각 노드의 값은 0 이상 9 이하이다. 
• 숫자 0003456과 같이 0이 앞서는 list는 주어지지 않는다.

---

Solution

• 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR))
  두 리스트의 중 길이가 긴 리스트를 s라 할 때, 적어도 한 번은 모든 노드의 값을 확인해야 하기 때문에 시간 복잡도는 O(s)이다.
• 고려사항
  1. 두 리스트의 길이가 같지 않을 수 있다.
  2. 두 리스트의 합은 두 리스트 중 긴 리스트보다 길어질 수 있다.
• Solution 1 (Brute force)
  어차피 두 수가 역순으로 주어지기 때문에 각 리스트의 처음부터 끝까지 탐색하며 더한 값을 새로운 노드의 값으로 하여 계속해서 추가해 나간다. 다만 더한 값이 10보다 carry가 발생하기 때문에 그 부분을 고려한다. 이런 식으로 해결 시 결국 시간 복잡도는 O(s)(s는 긴 리스트의 길이)로 BCR을 만족하기 때문에 시간 복잡도 측면에서 더 나은 알고리즘은 없다고 볼 수 있다.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode* copy = dummy;
        int carry = 0;

        while (l1 || l2 || carry)
        {
            int l1_val = l1 ? l1->val : 0;
            int l2_val = l2 ? l2->val : 0;

            copy->next = new ListNode(((l1_val + l2_val + carry) % 10));
            copy = copy->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;

            carry = ((l1_val + l2_val + carry) >= 10) ? 1 : 0;
        }

        return dummy->next;
    }
};

• Time complexity : O(s) // s는 두 리스트 중 긴 리스트의 길이
• Space Complexity :  O(s+1) // 가능한 최대 리스트 길이 + carry 가 발생할 경우
  
  

문제 출처 : https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

 

* 본 포스트 관련된 지적 및 조언은 모두 환영합니다.