[LeetCode] 2. Add Two Numbers 두 수의 덧셈

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

2번 Add Two Numbers는 주어진 두 연결리스트를 앞에서 부터 차례로 더하는 문제이다.

Example

 

# 풀이방법 1 - 반복문과 carry 이용 (내 풀이)

# 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]:
    
        root = result = ListNode()
        carry = 0
        
        while l1 or l2 :      
            
            if l1 is not None : 
                result.val += l1.val
                l1 = l1.next
            
            if l2 is not None :
                result.val += l2.val
                l2 = l2.next
            
            # carry 값 계산
            if result.val > 9 :
                carry = 1
                result.val -= 10
            
            if l1 is None and l2 is None and carry == 0:
                break
            
            # 올림 값 다음 노드에 추가
            result.next = ListNode(carry)
            result = result.next 
            carry = 0
         
            
        return root

| 아이디어  | 

연결리스트를 앞에서 부터 하나씩 접근하여 값을 더한다. 만약 carry 값이 발생한 경우, 더해준다.

 

| 핵심 | ⭐⭐⭐

root = result = ListNode()

: result를 가지고 코드를 다뤘지만, root를 출력하면 전반적인 연결리스트가 보여진다. 

 

 

 

# 풀이 방법 2 -  전가산기 풀이 (내 풀이와 비슷하지만 더 간단 / 책 풀이 참고)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        root, head = listNode(0)
        carry = 0
        
        whlie l1 or l2 or carry  :
        	sum = 0
            
            if l1 : 
            	sum += l1.val
            	l1 = l1.next
            
            if l2 : 
            	sum += l2.val
            	l2 = l2.next
            
            # 몫(자리올림수), 나머지 (값) 계산
            carry, val = divmod(sum+carry, 10)
            head.next = ListNode(val)
            head = head.next
            
        return root.next

| 흐름 | 

(풀이 1과 아이디어는 동일하지만 , carry 값 계산하는 방식에 divmod 함수를 이용하였고, 연결리스트 합은 sum 함수에 따로 저장을 하고 뒤에서 carry값과 sum을 더하는 부분에서 차이가 있다. 

 

 

| 핵심 |

# 몫(자리올림수), 나머지 (값) 계산
            carry, val = divmod(sum+carry, 10)
            head.next = ListNode(val)
            head = head.next

 

 

# 결과