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

오랜만에 알고리즘 포스팅..! LeetCode의 Top Interview Questions를 풀고 있다. LeetCode는 vscode에 확장팩이 있어서 홈페이지에 안들어가고 vscode에서 문제 읽기, 코드 작성, 테스트 및 작성까지 한 번에 할 수 있다. 이게 진짜 편해서 LeetCode를 포기할 수 없는데 solved.ac 뱃지가 탐나서 백준도 풀까 생각 중이다. 우선 당분간은 Top Interview Questions을 계속해서 풀 것 같다.

📌 문제

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

📝 풀이

링크드 리스트 문제는 릿코드를 기준으로 몇 문제 풀어보니까 유형이 아래와 같이 나뉘는 것 같다.

1. 기존의 리스트를 조작해야하는 경우

리턴을 요구하지 않고 기존의 링크드 리스트를 조작하라고 한다. 커서를 요리조리 잘 옮겨서 풀면 됨…

2. 새로운 리스트를 만들어야 하는 경우

두 개의 링크드 리스트가 주어지고 합치라던지, 교집합을 구하라고 하므로 새로운 링크드 리스트를 만들어야 한다. 본 문제도 이 유형에 해당한다. 새로운 링크드 리스트는 아래와 같이 만들면 된다. 코드는 206.reverse-linked-list.py, 21.merge two sorted lists.py 참고

 newHead = ListNode(0)
 cur = newHead

 while 조건문:
     # ...
     cur.next = ListNode(val)
     cur = cur.next

 return newHead.next # headNode의 값은 0이고 next부터 값을 넣었으므로 next 반환

3. 리스트를 빠르게 탐색해야 하는 경우

길이, 중간 위치, 병합 지점을 구해야 하는 경우이다. 두 개의 포인터를 사용해야 한다. slow와 fast라는 두 개의 러너 포인터를 만들어서 fast는 두 칸씩, slow는 한 칸씩 이동하여 fast를 기준으로 탐색이 끝났을 때 slow는 링크드 리스트의 가운데에 있으며, fast를 통해 길이를 구할 수 있다. 코드는 234.Palindrome-linked-list 참고

이 문제는 2번째 유형에 해당한다. 두 개의 링크드 리스트를 동시에 탐색을 시작한다. divmod를 사용해서 carry를 저장하였다. 이 때 한 개의 리스트가 끝까지 도달하면 첫 번째 while문을 끝낸다. 그리고 삼항연산자를 이용해서 길이가 긴 리스트를 l4가 가르키게 해서 탐색을 계속한다. 마지막으로 carry가 남아있는 경우 새로운 자릿수가 추가된 것이기 때문에 next에 1을 가진 노드를 붙여준다. 시간복잡도는 O(max(m,n))

Top voted Solution을 보니까 하나의 while문에서 l1, l2의 val을 계속 0으로 초기화하고 not l1, l2인 경우 val을 넣어주어서 처리해주는 코드를 봤다. 하나의 while문에서 해결할 수 있어서 더 깔끔한 것 같다.

Python 코드

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l3 = ListNode()
        cur = l3
        carry = 0

        while l1 and l2:  # 둘 중에 하나 끝까지 갔으면
            carry, val = divmod(l1.val+l2.val+carry, 10)
            l1 = l1.next
            l2 = l2.next
            cur.next = ListNode(val)
            cur = cur.next

        l4 = l1 if l1 else l2  # 남아있는 노드 계속 더함

        while l4:
            carry, val = divmod(l4.val+carry, 10)
            l4 = l4.next
            cur.next = ListNode(val)
            cur = cur.next

        if carry == 1:
            cur.next = ListNode(1)

        return l3.next