코딩테스트 공부

leetcode 문제 - midium

Add Two Sum :

python3

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.

My Solution

# 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):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        st1 = self.cvtString(l1)
        st2 = self.cvtString(l2)
        initialNode = None
        if len(st1) >= len(st2):
            initialNode = l1
            while l2 is not None:
                if l1.val + l2.val >= 10:
                    l1.val = (l1.val + l2.val) % 10
                    if l1.next is not None:
                        l1.next.val += 1
                    else:
                        l1.next = ListNode(1, None)
                    l1 = l1.next
                    l2 = l2.next
                else:
                    l1.val = l1.val + l2.val
                    l1 = l1.next
                    l2 = l2.next
            while l1 is not None:
                if l1.val >= 10:
                    l1.val = l1.val % 10
                    if l1.next is not None:
                        l1.next.val += 1
                    else:
                        l1.next = ListNode(1, None)
                    l1 = l1.next
                else:
                    return initialNode
            return initialNode
        else:
            initialNode = l2
            while l1 is not None:
                if l1.val + l2.val >= 10:
                    l2.val = (l1.val + l2.val) % 10
                    if l2.next is not None:
                        l2.next.val += 1
                    else:
                        l2.next = ListNode(1, None)
                    l1 = l1.next
                    l2 = l2.next
                else:
                    l2.val = l1.val + l2.val
                    l1 = l1.next
                    l2 = l2.next
            while l2 is not None:
                if l2.val >= 10:
                    l2.val = l2.val % 10
                    if l2.next is not None:
                        l2.next.val += 1
                    else:
                        l2.next = ListNode(1, None)
                    l2 = l2.next
                else:
                    return initialNode
    
    def cvtString(self, l):
        num = ""
        while(l is not None):
            num += str(l.val)
            l = l.next
        return num

너무 길게 쓴거 아닌가 싶다...

3번 시도만에 통과 (문제를 대충 읽어서 뻘짓을 두번 했다.)
속도는 매우 빨랐지만 더 짧은 코드는 없을까 고민
시간 복잡도는 O(n) 이지 않을까...?

Better Solution

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        res = dummy = ListNode()
        carry = 0
        while l1 or l2:
            v1, v2 = 0, 0
            if l1: v1, l1 = l1.val, l1.next
            if l2: v2, l2 = l2.val, l2.next
            
            val = carry + v1 + v2
            res.next = ListNode(val%10)
            res, carry = res.next, val//10
            
        if carry:
            res.next = ListNode(carry)
            
        return dummy.next

discussion에 훨씬 깔끔하고 짧은 코드가 있다.
주먹구구식으로 여러 예외 케이스들을 조건문으로 처리하느라 쓸데없이 코드가 길어졌다. 시간복잡도는 O(n)으로 동일. 속도는 내가 조금 더 빠르긴 한데
가독성이 높은 코드를 작성하기 위한 공부가 필요할꺼같다.
화이팅.