[Python] 2. Add Two Numbers

문제

2. Add Two Numbers

두 개의 비어있지 않은 링크드 리스트가 주어진다. 

각 노드는 0 또는 자연수로 채워져있다. 숫자는 역순으로 저장돼있고, 두 노드의 각 숫자의 합을 연결 리스트로 반환한다.

Example 1

l1 = [2, 4, 3], l2 = [5, 6, 4]라면 결과는 [7, 0, 8]이 나와야 한다.

말 그대로 두 링크드 리스트에서 각 노드의 숫자를 합해서 하나의 노드로 만든다는 말이다.

2 + 5 = 7

4 + 5 = 10 이지만 제한 사항에 다음과 같은 내용이 있다. (0 <= Node.val <= 9)

10은 9보다 크기 때문에 1을 다음 두 노드 간의 합에 반영한다.

이렇게 342 + 464 = 807이라고 돼있는 설명이 더 헷갈리게 한다🤪

노드의 값이 0과 9사이 값이라는 걸 제한사항이 아닌 문제 위쪽에 적어주는 것이 덜 헷갈릴 것 같다.

풀이 과정

풀이 시간: 35분

알고리즘: 링크드 리스트

 

1. answer를 Dummy Node로 만들어 놓고, 현재 노드(cur) 역시 answer에서 시작한다.

2. l1과 l2에 val가 있다면 각 노드의 숫자를 꺼내와 합을 구한다.

3. 그 합을 노드로 만든 후 cur.next가 해당 노드를 가리키게 한다.

4. 현재 노드(cur)은 방금 만든 합 노드로 갱신한다.

 

시간 복잡도: O(max(n, m))

각 연결 리스트 순회: l1의 길이를 n, l2의 길이를 m이라고 한다면, 각 연결 리스트의 모든 노드를 순회하면서 링크드 리스트를 만들어야 하기 때문에 O(max(n, m))이 된다.

코드

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        """
        :param l1: first linked list
        :param l2: second linked list
        :return: sum of both linked lists
        """
        flag = 0 # 자릿수 올림을 저장할 변수
        answer = ListNode() # 더미 헤드 노드
        current = answer

        while l1 or l2 or flag:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # 현재 자리의 합 계산
            total = val1 + val2 + flag
            flag = 1 if total > 9 else 0
            current.next = ListNode(total % 10)

            # 다음 노드로 이동
            current = current.next

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return answer.next

재귀로도 풀이할 수 있는데 그냥 단순하게 cur 을 사용해서 구현했다.

Linked List 이용한 문제를 오랜만에 푸는데 재밌었다.

LeetCode는 미리 정의된 클래스 ListNode 와 같은 것들을 활용해서 문제를 풀어야 하는 경우들이 있어서 독특한 것 같다.

안그랬음 그냥 eval 사용해서 합 구한 후 리스트로 반환했을텐데, next에 다음 노드의 주소를 저장함으로써 논리적 연속성을 유지하는 링크드 리스트의 특성을 활용해 풀어야해서 재밌었다.