[LeetCode] 2. Add Two Numbers

LeetCode 2번 Add Two Numbers

math, LinkedList

 

---

 

문제

반대의 값이 저장된 두 개의 LinkedList가 주어지고 원래 두 정수의 합을 다시 LinkedList로 반환하는 문제이다.

 

1번 예제를 보면 342 + 564 = 807이고 이를 역순한 708이 답이다.

오랜만에 보는 LinkedList 문제였다.

 

3번 예제 같은 경우엔 9999999 + 0009999 = 10009998 이 되고

이를 역순한 89990001이 답이 되는 것

 

제약사항은 다음과 같다.

 

 

과정

처음에 문제를 읽어봤을 때 무슨 소리인지.. 여러번 봤는데 이해하고 나면 단순한 문제임을 알 수 있다.

 

합산을 하는 과정은 주어진 LinkedList인 l1과 l2를 처음부터 차례대로 더하면 된다.

왜냐하면 어차피 각 정수가 역순으로 되어있어서 리스트를 순서대로 계산하면 일의 자리부터 접근할 수 있기 때문이다.

 

즉, 두 LinkedList를 앞에서부터 접근하면서 더해주는 식으로 새로운 LinkedList를 만들면 정답이 된다.

하나 생각해야 할 부분은 중간에 정수의 합산의 값이 10을 넘어갈 때 올림 처리만 진행해 주면 된다는 것이다.

 

 

1. 나의경우 carry라는 승수를 담을 변수를 선언했다.

2. carry에 l1과 l2의 정수에 대해서 합산을 진행하고 나누기 연산을 수행해서 새로운 ListNode에 나머지 값을 넣어주고 몫 연산을 수행해서 다음 자리수로 넘길 승수를 그대로 carry변수에 남겨줬다.

3. 또한 while 반복문을 수행할 때도 승수가 있는지 없는지를 계산해야 하므로 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]:
        node = ListNode()
        cur = node
        carry = 0
        while l1 or l2 or carry:    # 예제 3번처럼 승수만 뒤로 넘겨지는 경우도 있으니 carry를 조건에 추가
            if l1:
                carry += l1.val
                l1 = l1.next 
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry % 10)    # 나머지 저장
            cur = cur.next
            carry = carry // 10    # 몫 저장
        return node.next

 

 

통과

 

---

 

// 2023-08-03 스터디 과제