2021-01-13] Add Two Numbers

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/580/week-2-january-8th-january-14th/3601/

 

확실히 주말에 힘든 문제인것 같은 느낌이다! 다행이 오늘 문제도 풀 수 있었다~

자 예시를 보며 문제를 이해하자.

 

<문제 예시 1-3>

 

입력 값으로 ListNode 2개를 준다. 그 값이 더해져 값을 넘겨주는 것. 

설명을 보면 결국 ListNode의 합산된 값의 새로운 List를 달라는 말이다.

 

문제풀이 1차)

list의 시작부터  l1의 첫번재값*10의0승 = 첫째자리의 값 을 이용하여,

list 마다 가진 값을 만들고, 둘을 합해 역순으로 list를 만들어 보는 방법을 선택했다.

 

# 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
        """
        cnt=0 # 자리수 계산을 위한 변수
        sumval=0 # 합쳐진 값을 위한 변수
        while l1!=None:
            sumval=sumval+l1.val * (10 ** cnt) # 뒤로가면서 자리수를 늘려 값을 구한다.
            cnt=cnt+1
            l1=l1.next
        cnt=0
        while l2!=None:
            sumval=sumval+l2.val * (10 ** cnt)
            cnt=cnt+1
            l2=l2.next
        #print(sumval)
        ans = ListNode(0) # 초기값 0이 있어서 마지막에 next값을 반환 예정
        for i in str(sumval)[::-1]: # sumval의 역순으로 문자를 받아 list value로 쓴다.
            tempNode = ListNode(i)
            p = ans
            while p.next != None:
                p=p.next
            p.next=tempNode
        ans = ans.next # 선언한 dummy list의 다음부분이 정답
        return ans

<1차 문제풀이 성능>

 

 

 

문제풀이 2차)

성능이 더 좋을 줄 알고, 만들어본 코드

# 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: ListNode, l2: ListNode) -> ListNode:
        of=0
        ans=ListNode(0)
        ep=ans
        while l1!=None and l2!=None:
            print(l1.val+l2.val+of)
            if l1.val + l2.val + of >= 10:
                newval=(l1.val+l2.val+of)%10
                of=int((l1.val+l2.val+of)/10)
            else:
                newval=l1.val+l2.val+of
                of=0
            #print(newval,of)
            temp = ListNode(newval)
            p=ep
            p.next=temp
            ep=temp
            l1=l1.next
            l2=l2.next
        if l1!=None:
            while l1 !=None:
                if l1.val+of>=10:
                    newval=(l1.val+of)%10
                    of=int((l1.val+of)/10)
                else:
                    newval=l1.val+of
                    of=0
                temp=ListNode(newval)
                p=ep
                p.next=temp
                ep=temp
                l1=l1.next
        else:
            while l2 !=None:
                if l2.val+of>=10:
                    newval=(l2.val+of)%10
                    of=int((l2.val+of)/10)
                else:
                    newval=l2.val+of
                    of=0
                temp=ListNode(newval)
                p=ep
                p.next=temp
                ep=temp
                l2=l2.next
        if of != 0:
            temp=ListNode(of)
            p=ep
            p.next=temp
            ep=temp
        return ans.next

 

<2차 문제풀이 성능>

왜 시간/메모리 둘다 더 잡아먹게 되었는지.. 이해가 잘 안된다.. ㅠ 

 

어려운 알고리즘의 세계..