Leetcode 02. Add Two Numbers

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

Add Two Numbers - LeetCode

문제. 2개의 linkedlist가 주어졌을 때 각 항목을 더한 결과값을 reverse order로 반환하는 코드를 짜라.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

 

---

 

모범 답안)

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = dummy
        carry = 0           #10의 자리를 담는 그릇
        
        while l1 or l2 or carry != 0:
            l1val = l1.val if l1 else 0
            l2val = l2.val if l2 else 0
            
            sum = l1val + l2val + carry
            
            carry = sum//10				#각 요소의 덧셈으로 나오는 10의 자리를 담고
            new = ListNode(sum%10)   #나머지를 노드에 담아주고
            curr.next = new			#next에 나머지 값을 담고
            curr = new				# 현재 노드를 새로운 값으로 담아줘서 노드가 이동하도록 함
            
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next 			#0을 제외한 결과값이 나오도록 함

 

이 답안을 이해하는데에 시간이 좀 걸렸는데요, 코드를 하나하나 뜯어보겠습니다!

 

dummy = ListNode(0)  

#정답을 담을 그릇을 만드는데, 반환되는 결과값이 LinkedList여야 하기 때문에 노드의 형태로 저장을 해야합니다. None으로 저장을 할 시에는 , 뒤에 next를 붙이는 노드 형식의 표현이 불가하기 때문에 에러가 발생합니다. 그래서 임의로 0이라는 값을 가진 List Node를 만듭니다

 

curr = dummy

#curr이라는 현재 노드값을 담는 그릇이 필요한데 두 LinkedList를 계산하는 과정이 아직 시작되지 않았기 때문에, 일단 값이 0인 노드에 있겠죠? 그래서 dummy값을 curr에 담아줍니다

 

 carry = 0

#carry는 6+6 = 12일 때, 앞의 자리수에 더해지는 10의 자리를 킵해두는 변수가 필요하기 때문에 초기에 0으로 세팅합니다
        
        while l1 or l2 or carry != 0:

# 여기서 l1과 l2의 경우 노드에 있는 값을 뽑아야 하기 때문에 while문이 자연스럽지만, carry에 의문이 들 수 있는데요.

결론적으로 carry !=0 을 생략하면 에러가 나는데 그 이유는 l1과 l2의 값을 모두 다 계산 했는데 마지막 자리수가 10의 자리수를 넘어가는 값이 나오면 그 값을 처리하지 않고 마무리 되는 경우를 방지하기 위해서 입니다

 

            l1val = l1.val if l1 else 0
            l2val = l2.val if l2 else 0

 

#여기는 l1과 l2값이 none이 아니라면 하나씩 뽑아 보자는걸 한 줄에 깔끔하게 표현한 식입니다
            
            sum = l1val + l2val + carry

#이제 요소들을 한 자리씩 계산을 시작해보는데요

      
            carry = sum//10   

#초기 변수 세팅의 목적에 맞게 10의 자리수를 담아주고

            new = ListNode(sum%10)

#new라는 노드에 나머지를 담아준 뒤,
            curr.next = new

#현재 변수의 다음 값에 결과로 나온 나머지 값을 넣고
            curr = new

#노드 이동을 위해서 현재 변수를 new값으로 이동시켜 놓습니다. 
            
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

# 식이 돌아갈 때, l1.next, l2.next로 이동해둬야 위의 l1.val, l2.val이 그 다음값으로 넘어가기 때문에 이 식을 넣어줍니다

        return dummy.next

#여기서 왜 dummy를 안 넣고 dummy.next를 넣는지 궁금했는데요, dummy만 출력해보니 앞에 0 값이 포함되어 나오더라구요. dummy라는 리스트 노드의 첫 값에 0이 포함되어 있기 때문에 그 값을 제외해서 출력해야하기 때문에 dummy.next를 표현한 거죠

 

---

리스트노드는 재밌지만 참 손이 많이 가는 데이터 구조인 것 같습니다 ㅎㅎㅎ

다른 리스트 노드 문제를 가져와서 리스트노드를 정복해보겠습니다!!!!