[LeetCode C++] 2. Add Two Numbers

⭐️ 난이도

Medium

 

---

⭐️ 문제

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

Add Two Numbers - LeetCode

음수가 아닌 정수가 들어있는 비어있지 않은 linked list가 두 개 주어진다.

자리 수가 반대 순서로 (즉 1의 자리부터) 주어지며, 각 노드에 해당하는 값은 한 자리 수 이다.

두 개의 수를 더한 후, 합을 linked list로 반환하라.

 

단, 0으로 시작하는 숫자는 올 수 없다. (0은 제외)

 

---

⭐️ Follow-up

X

 

---

⭐️ Idea flow

먼저 이 문제 자체에서 ListNode라는 구조체가 주어진다.

이 구조체에는 int형 변수 val과, 다음 노드를 가리키는 ListNode형 포인터 next가 있다.

그 밑으로 있는 코드들은 생성자를 매개변수에 따라 오버로딩한 것들이다.

 

주어지는 두 개의 ListNode l1과 l2는 일의 자리부터 접근이 가능하다.

예를 들어 l1이 2 -> 4 -> 3이면 이 수는 342인 것이고, l2가 5 -> 6 -> 4이면 이 수는 465인 것이다.

 

그런데 생각을 해보면 우리는 덧셈을 할 때에 일의 자리부터 시작을 한다. 일의 자리의 수를 더했을 때

1) 만약 합이 10이 넘지 않는다면 : 해당 자리 수에 더한 값을 넣는다.

2) 만약 합이 10을 넘는다면 : 해당 자리 수에 합의 일의 자리 수만 넣고, 이후의 값은 다음 자리에서 더할 때 같이 더한다.

 

그리고 주어진 ListNode 또한 일의 자리부터 접근이 가능하기 때문에 우리가 생각하는 통상적인 더하기를 하면 된다!

 

우선 더한 값을 ListNode 형태로 반환해야 하기 때문에 ListNode* l3 = new ListNode();를 통해 생성해준다.

 

두 번째로, int형 변수 sum을 선언하고 l1와 l2의 val을 더한다.

sum의 결과에 상관없이 우선 일의 자리 수만 취하면 되기 때문에, sum % 10의 값을 오버로딩 생성자를 통해 전달해준다.

l3->next = new ListNode(sum % 10);

위와 같이 하면 val 값이 sum % 10인 ListNode 객체를 만든 후, l3에 연결이 된다.

l3 = l3->next를 통해 l3의 위치를 다음 노드로 이동시켜주고, sum /= 10을 통해 십의 자리만 남겨둔다.

 

위와 같은 과정을 계속 반복하다가 

1) l1이 null을 가리킬 때 (값이 더 이상 없을 때)

2) l2가 null을 가리킬 때 (값이 더 이상 없을 때)

3) sum이 0일 때 (올림값이 없을 때)

세 가지 조건을 모두 만족하면 더하기 과정이 모두 끝난 것 이므로, l3의 시작 노드->next를 전달하면 된다.

 

 

이렇게 하면 반복문을 l1.size()와 l2.size() 중 더 큰 수 만큼 돌기 때문에, 시간 복잡도 또한 O(l1.size()) 혹은 O(l2.size())가 될 것 이다.

 

---

⭐️ Code

/**
 * 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) {
        ListNode* l3 = new ListNode();
        ListNode* dummy = l3;
        int sum = 0;

        while(l1 != nullptr || l2 != nullptr || sum){
            if(l1 != nullptr){
                sum += l1->val;
                l1 = l1->next;
            }
            if(l2 != nullptr){
                sum += l2->val;
                l2 = l2->next;
            }
            
            l3->next = new ListNode(sum % 10);
            sum /= 10;
            l3 = l3->next;
        }

        return dummy->next;
    }
    
    // Time complexity : O(max(l1.size(), l2.size()))
};

 

 

---

⭐️ Feedback

문제 자체에 주어진 ListNode 구조체가 있어서 그런지 풀이 방법이 다양할 여지가 별로 없었던 것 같다.

다만 문제를 처음 봤을 때, 내가 정의한 구조체가 아니라 문제 자체에서 주어진 구조체다보니 당황스럽긴 했다.

하지만 이해하는데에 그렇게 어렵진 않아서 푸는데에 많이 힘들진 않았다.

 

다만 while문의 sum과 관련된 조건과, return 할 때에 dummy->next를 return 해야 하는 것과 같은 세심한 것에 아직 약하다는 것을 알 수 있었다.

 

문제를 좀 더 꼼꼼하게 읽고, 알고리즘도 전체적인 플로우 뿐 만 아니라 세부적인 부분 또한 조금 더 신경을 써야겠다.