[LeetCode] 2. Add Two Numbers

말하는 감자·2024년 12월 4일

data structure leetcode linked list python recursion 리트코드 연결 리스트 자료구조 재귀 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

25/32

오늘부터는 본격적으로 연결 리스트의 medium 레벨의 문제를 풀려고 합니다.

1. 오늘의 학습 키워드

Linked List
Recursion

2. 문제: 2. Add Two Numbers

단계: Medium
주제: Linked List, Math, Recursion
출처: https://leetcode.com/problems/add-two-numbers/description/

Description

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.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

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.

3. 문제 풀이

Step1. 문제 이해하기

개인적으로 해당 문제를 이해하는데 조금 걸렸습니다. 오히려 예시 설명이 더 헷갈렸습니다.. 쉽게 보자면 다음과 같습니다.

두 개의 non-empty 연결 리스트가 주어집니다. 주어진 두 개의 연결 리스트를 더한 결과를 새로운 연결 리스트로 반환하는 문제입니다.

말 그대로 두 개의 연결 리스트 l1과 l2가 [2, 4, 3], [5, 6, 4]가 있으면 각 자리숫자를 더한 값을 연결 리스트로 나타내면 됩니다. 합이 10이 넘어가면 나머지를 다음 노드에 넘겨주면 됩니다.

이제 문제 입출력을 살펴보도록 하겠습니다.

Input:
- 주어진 연결리스트의 노드 개수는 1이상 100이하입니다.
- 시간 복잡도는 충분합니다.
- 연결 리스트에 맨앞에 노드가 0을 가리키지는 않는다고 합니다. 단 0만 있을때는 가능합니다.
Output:
- 두 개의 연결 리스트의 각 요소를 더한 새로운 연결 리스트를 반환합니다.

Step2. 문제 분석하기

첫 번째 예시를 살펴보겠습니다.

l1 = [2, 4, 3]
l2 = [5, 6, 4]

2와 5를 더하면 7, 4와 6을 더하면 10이며 10은 노드 값이 될 수 없습니다. 그렇기 때문에 나머지를 노드값, 몫을 다음 노드에 추가합니다. 그렇다면 두 번째 노드 값은 0, 세 번째 노드 값은 1 + 3 + 4로 8이나옵니다. 즉, 결과는 [7, 0, 8] 이 나오게 됩니다.

두 연결 리스트를 순회하면서 위처럼 구현하면 충분히 해결될 것으로 보입니다.

그럼 코드 설계를 하러 가볼까요?

Step3. 코드 설계하기

Step2에서 사용했던 예시를 아래처럼 표현해보았습니다.

초기화는 다음과 같이 진행합니다

carry라는 변수를 0으로 초기화 설정을 합니다.
새로 만들어질 연결 리스트를 위해 더미 노드를 설정합니다.

이것을 기반으로 코드 구현을 진행하도록 하겠습니다. 그런데 이 방법은 두 개의 연결 리스트를 반복문을 통해 순회하면서 진행합니다. 이는 재귀로도 가능할 것으로 보입니다.

반복문 방식:

변수 초기화:
- carry: 자리 올림 값을 저장.
- dummy: 새 연결 리스트를 구성할 더미 노드.
- curr: 현재 노드를 가리키는 포인터.
연결 리스트 순회:
- 두 연결 리스트(l1, l2)의 노드를 순회하며 자리수를 더함.
- 자리 올림(carry)를 계산하여 다음 노드에 반영.
결과 연결 리스트 반환:
- 더미 노드의 다음 노드를 반환.

재귀 방식:

기저 사례:
- 두 연결 리스트가 모두 비었고 자리 올림(carry)이 없으면 종료.
계산:
- 현재 자리의 값을 계산(val1, val2 및 carry 포함).
다음 노드로 이동:
- 현재 계산 결과를 새로운 노드로 추가.
- l1, l2의 다음 노드 및 carry를 재귀 호출에 전달.

따라서, 코드는 두 가지로 진행하도록 하겠습니다.

Step4. 코드 구현

반복문

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    # 1. Linked List
    def addTwoNumbers(self, l1, l2):
        # https://leetcode.com/problems/add-two-numbers/submissions/1469870730/
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy = ListNode()  # 더미 노드 생성
        curr = dummy  # 현재 노드 포인터
        carry = 0  # 올림 값 초기화

        # l1, l2 또는 carry가 존재하는 동안 반복
        while carry or l1 or l2:
            if l1:
                carry += l1.val
                l1 = l1.next  # l1의 다음 노드로 이동
            if l2:
                carry += l2.val
                l2 = l2.next  # l2의 다음 노드로 이동
            
            # 현재 자리수 계산 및 연결
            curr.next = ListNode(carry % 10)  # 자릿수 값 생성
            carry //= 10  # 올림값 업데이트
            
            # 다음 노드로 이동
            curr = curr.next
        
        # 결과로 더미 노드의 다음 노드 반환
        return dummy.next

코드 설명:
- dummy와 curr로 새로운 연결 리스트를 만듭니다.
- while 반복문에서 두 리스트와 자리 올림(carry)을 모두 처리.
- 자리 올림이 있을 때도 추가 노드 생성 가능.
시간 복잡도: $O(max(m,n))$ , 여기서 m과 n은 각각 l1과 l2의 길이입니다. 두 리스트를 완전히 순회합니다.
결과: https://leetcode.com/problems/add-two-numbers/submissions/1469870730/

재귀

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2,carry=0):
        # https://leetcode.com/problems/add-two-numbers/submissions/1469872346
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        
        # base case
        if not l1 and not l2 and carry == 0:
            return None

        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry

        node = ListNode(total % 10)

        node.next = self.addTwoNumbers(
            l1.next if l1 else None,
            l2.next if l2 else None,
            total // 10
        )

        return node

코드 설명:
- 노드 값을 합산한 결과를 새 노드로 생성.
- 자리 올림을 다음 재귀 호출로 전달.
- 재귀 종료 조건: l1, l2가 없고 자리 올림이 없을 때.
시간 복잡도: $O(max(m,n))$ , 여기서 m과 n은 각각 l1과 l2의 길이입니다. 두 리스트를 완전히 순회합니다.
결과: https://leetcode.com/problems/add-two-numbers/submissions/1469872346