[알고리즘/Python] LeetCode 2. Add Two Numbers

📑 1. 문제 이해

https://leetcode.com/problems/add-two-numbers/?envType=study-plan-v2&envId=top-interview-150 

Add Two Numbers - LeetCode

이 문제는 양수를 나타내는 연결 리스트를 사용해서 그 합을 구하는 것입니다. 연결리스트는 어떤 양수를 거꾸로 읽은 것으로 [2,4,3]은 숫자 342를 나타냅니다. 연결리스트의 길이는 최소 1 최대 100, 각 노드의 값을 0에서 9까지이므로 연결리스트는 0에서 9 * 10^99 까지의 숫자를 표현합니다. 그 합도 연결리스트 형태로 만들어서 그 head를 반환해야 합니다.

 이때 주의할 점은 결과 연결리스트의 길이는 최대 101이 될 수 있다는 것입니다. 99 + 99 = 198로 두자리수를 더한 수는 최대 세자리가 될 수 있습니다. 따라서 100자리수 두개를 더하면 최대 101자리가 됩니다.

☑️ 테스트케이스

문제에서 주어진 테스트 케이스는 다음과 같습니다.

 

1) Example1: l1= [2,4,3],  l2=[5,6,4]

    - 두 수의 자리수가 같고, 두 수의 합도 세자리수이다.

2) Example1: l2= [0],  l2=[0]

   - 두 수 자리수가 같고 그 결과가 0이다.

3) Example1: l1= [9,9,9,9,9,9],  l2=[9,9,9,9]

   - 두 수의 자리수가 다르고, 두 수의 합이 두 연결리스트의 길이보다 길다.

 

이때 주의할 것은 실제 매개변수로 들어오는 것은 l1, l2배열이 아니라, 연결리스트의 head라는 점입니다. 즉 채점시에는 다음과 같이 input 배열을 연결리스트 형태로 반환한 후 그 연결리스트를 사용해 우리가 제출한 답안을 테스트할 것입니다.

def makeLinkedList(arr: List[int]) -> ListNode:
    head = ListNode(-1, None)
    curr = head
    for n in arr:
        curr.next = ListNode(n, None)
        curr = curr.next
    return head.next

l1 = makeLinkedList([2, 4, 3])
l2 = makeLinkedList([5, 6, 4])

Solution.addTwoNumbers(l1, l2)

💡 2. 알고리즘 설계

일반적으로 두 수를 덧셈하는 과정과 같습니다. 우리는 1의 자리부터 더해가며 그 값이 10을 초과하면 1을 올려준 후 그 나머지가 그 자리의 수가 되는 과정을 반복하며 덧셈을 합니다.  연결리스트의 head가 1의자리를 의미하므로 각 연결리스트의 head부터 그 합을 더하고 그 합이 10을 넘으면 1을 올려줍니다.

 

1. 두 연결리스트의 합을 기록할 새로운 연결리스트를 초기화합니다. 이때 dummy head를 추가하여 첫번째 노드 추가도 두번째노드 추가와 똑같이 처리할 수 있습니다. 결과값 반환시에는 dummy head가 아닌 head를 반환합니다. prev는 새로운 연결리스트를 가리키는 포인터입니다. p1, p2는 각각 l1, l2의 노드를 가리키는 포인터로 head를 가리키도록 초기화합니다.

2. 두 노드의 합을 더합니다. 이전 자리수에서 1이 올라왔다면 그 값도 더해줍니다. 이때 주의할 점은 두 연결리스트의 자리수가 달라서 포인터가 None을 가리킬 수 있다는 점입니다. 

3. 그 합이 10을 초과한다면 다음 자리수로 1을 올린다는 의미로 up을 True로 갱신하고, sum에서 10을 빼줍니다.

4. 그 결과를 가지고 새로운 노드를 만든 후, 연결리스트의 마지막에 추가해줍니다.

5. prev, p1, p2 포인터를 한 칸 전진합니다.

6. 두 연결리스트의 끝까지 전진한 후, 이전 자리수에서 넘겨진 수도 없을때까지 반복합니다.

    - [9] 와 [99]를 합칠때 두 연결리스트의 끝까지만 전진한다면 그 결과는 [8, 0]이 됩니다. 마지막에 올려진 1까지 더해주어야 [8,0,9]로 의도한 값이 됩니다.

7. 새로운 연결리스트의 head를 반환합니다(dummy 아닌 실제 head)

def solution(l1: ListNode, l2: ListNode) -> ListNode:
    p1 = l1
    p2 = l2

    head = ListNode(-1, None)
    prev = head

    up = False
    while p1 or p2 or up:
        sum = (p1.val if p1 else 0) + (p2.val if p2 else 0) + up
        if sum >= 10:
            up = True
            sum -= 10
        else:
            up = False

        new_node = ListNode(sum, None)
        prev.next = new_node
        prev = new_node

        p1 = p1.next if p1 else None
        p2 = p2.next if p2 else None

    return head.next

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 두 연결리스트의 각 노드를 최대 1번씩만 방문합니다. 

공간 복잡도: O(N). 두 연결리스트 중 긴 연결리스트만큼의 혹은 그보다 한 개의 노드가 추가된 공간이 필요합니다.

 ⎌ 3. 검토

앞서 본 테스트 케이스를 검토한 결과를 다음과 같습니다.

 

1) Example1: l1= [2,4,3],  l2=[5,6,4]

    - 두번째 자리수의 합이 10으로 1을 다음자리수로 넘겨줄 수 있습니다

.

2) Example1: l2= [0],  l2=[0]

   - 새로운 연결리스트에 값이 0인 새로운 노드가 추가된 후 반복문이 종료됩니다. 연결리스트가 끝나 p1, p2가 None을 가리키고, 이전 자리수의 합이 0을 초과하지 않아 up이 False를 가리킵니다.

 

3) Example1: l1= [9,9,9,9,9,9],  l2=[9,9,9,9]

   - 두 연결리스트 합의 자리수가  l1의 자리수보다 커집니다. 연결리스트의 끝에 도달해 p1, p2가 None을 가리키더라도 up이 True를 가리켜 한번 더 while문 안으로 진입합니다. 값이 1인 새로운 노드를 추가한 후 반복문이 종료됩니다.

---

🤔 다른 사람의 풀이

 새로운 연결리스트를 만들지 않고 주어진 연결리스트의 공간을 재활용함으로써 공간 복잡도를 줄일 수 있습니다. 두 수의 합은 두 수 중 큰 수와 자리수가 같거나 한 자리수만 추가됩니다. 

 

1. 두 연결리스트를 더한 값을 l1에 갱신해 값니다. 둘 중 하나의 연결리스트가 끝난다면 즉 l1, l2 중 하나가 None을 가리킨다면 반복문을 종료합니다. 

2. 만약 l1이 None이고 l2가 노드를 가리킨다면, l1보다 l2자리수가 크다는 의미입니다. l2포인터를 마지막으로 갱신된 노드의 next에 연결합니다.

3. l1 포인터를 전진하며 덧셈을 수행합니다.

4. l1의 head를 반환합니다. 

    def addTwoNumbers2(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = l1
        prev = None

        carry_over = 0
        while l1 and l2:
            raw_val = carry_over + l1.val + l2.val

            l1.val = raw_val % 10
            carry_over = raw_val // 10

            prev = l1
            l1 = l1.next
            l2 = l2.next

        if l2:
            prev.next = l2
            l1 = l2

        while l1:
            raw_val = carry_over + l1.val
            l1.val = raw_val % 10
            carry_over = raw_val // 10
            prev = l1
            l1 = l1.next

        if carry_over > 0:
            prev.next = ListNode(carry_over)

        return head

이를 그림으로 나타내면 다음과 같습니다.  l1과, l2가 다음과 같을때, 

두 연결리스트 중 하나가 끝날때까지 덧셈을 수행한 결과를 다음과 같습니다. 두번째 연결리스트가 더 길다면 마지막노드의 링크가 l2를 가리키도록 합니다.

덧셈을 끝까지 수행한 결과는 다음과 같습니다. 첫번째 연결리스트의 head를 반환합니다.

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N).  두 연결리스트의 각 노드를 최대 1번씩만 방문합니다. 

공간 복잡도: O(1). 기존의 연결리스트를 활용함으로써 최대 1개의 노드만 추가됩니다.

✅ 정리

◎ 연결리스트가 어떤 양수를 나타낼 수 있습니다. 

◎ 두 연결리스트를 합칠때 기존의 공간을 활용한다면 공간 복잡도를 줄일 수 있습니다.