LeetCode 2(Add Two Numbers, Python)

1. 문제 링크

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

Add Two Numbers - LeetCode

2. 문제 설명

• 두 개의 연결리스트는 역순으로 된 숫자를 나타내고, 각 노드는 한 자리 숫자만을 담고 있을 때, 이 두 숫자를 더하여 새로운 연결리스트로 반환하는 문제.
  
  • 예시1) l1 = [2,4,3], l2 = [5,6,4] 일 때, 역순인 342와 465를 더한 807의 역순 연결리스트인 [7,08]을 반환 
  • 예시2) l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 일 때, 역순의 합인 10009998의 연결리스트인 [8,9,9,9,0,0,0,1]을 반환

3. 처음 풀이

• 깔끔한 풀이가 아니라 아쉽긴 한데, 두 연결리스트의 노드 개수가 다른 케이스 때문에 깔끔히 작성이 안되긴 했다.
  • 우선 l1과 l2가 값이 존재할 때까지는
    • head.next에 l1.val + 12.val을 10으로 나눈 나머지를 넣고, 몫 (1)을 keep이라는 변수에 넣어둔다
    • head, l1, l2를 한 칸 이동시킨다
    • 그리고 keep이 0이 아니라면, l1이나 l2의 val에 1을 더한다음, keep을 0으로 리셋한다 
    • 만약 두 값을 더한게 10보다 작다면, 그냥 그 값을 head.next에 넣고, l1,l2, head를 한 칸 이동시킨다 
  • 그리고 l1만 남았을 때, l2만 남았을 때 그 값을 head.next에 넣어주는 작업을 한다
    • 여기서도 keep 이 0이 아닐 때는 값을 더해주는 작업을 했다. 
  • runtime이 68%로 나쁘진 않았는데, 코드에 많은 개선이 필요해보이긴 하다.

# Definition for singly-linked list.
# 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]:
        
        head_ = ListNode(0)
        head = head_ 
        keep = 0

        # 둘다 값이 있을 때
        while l1 and l2: 
            if l1.val + l2.val >= 10 and keep == 0: # keep 한 게 없을 때
                head.next = ListNode((l1.val + l2.val)%10) # 나머지 append
                keep = (l1.val + l2.val)//10 # 몫 keep 
                head = head.next # head 이동 시킴
                l1,l2 = l1.next,l2.next

            elif keep != 0: 
                if l2 is None:
                    l1.val +=1 # l1이든 l2든 한 개 + 시키고 
                    keep = 0 # keep 0으로 reset
                elif l1 is None:
                    l2.val +=1 
                    keep = 0
                else:
                    l1.val +=1
                    keep = 0 

            elif l1.val + l2.val < 10:
                head.next = ListNode(l1.val + l2.val)
                head = head.next 
                l1,l2 = l1.next, l2.next

        # 이제 l1만 남았을 때
        while l1:
            if keep != 0:
                l1.val +=1 
                keep = 0 
            elif l1.val >= 10: # 10이 되면
                head.next = ListNode(l1.val % 10) # 10으로 나눈 나머지
                keep = l1.val // 10 
                head = head.next
                l1 = l1.next
            else:
                head.next = ListNode(l1.val)
                head = head.next
                l1 = l1.next


        while l2:
            if keep != 0:
                l2.val +=1 
                keep = 0 
            elif l2.val >= 10: # 10이 되면
                head.next = ListNode(l2.val % 10) # 10으로 나눈 나머지
                keep = l2.val // 10 
                head = head.next
                l2 = l2.next
            else:
                head.next = ListNode(l2.val)
                head = head.next
                l2 = l2.next

        if keep != 0:
            head.next = ListNode(1)
            head = head.next 

        return head_.next

 

4. 다른 풀이

• 로직은 동일한데 훨씬 깔끔하다
  • 처음 풀이에서는 l1 또는 l2만 남았을 때 따로 빼줘야한다고 생각했는데,
    
    • while문을 l1 or l2 or carry(내 풀이에서는 keep)으로 두고, 
      • l1, l2를 옮기는 조건을, l1, l2가 None이 아닐 때로 해서 한큐에 해결. 

# Definition for singly-linked list.
# 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]:
        dummy = ListNode()
        cur = dummy
        carry = 0

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

            carry = val // 10
            val = val % 10

            cur.next = ListNode(val)
            cur = cur.next

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

        return dummy.next

5. 배운 점

• 다른 사람들 코드를 보면 배울 점이 많다. 어떻게 해야 좀 더 깔끔하고 직관적이게 작성할 수 있을지 고민