LeetCode 2. Add Two Numbers (Python3)

 

안녕하세요. 죠쵸입니다.

이번 문제는 LeetCode 2번 문제로 난이도는 MEDIUM 입니다. 지난 번 문제에 이어서 Linked List 의 자료구조를 처리하는 문제입니다.

leetcode.com/problems/add-two-numbers

Add Two Numbers - LeetCode

 

#LeetCode 2. Add Two Numbers(Description)

 

두개의 정수로 이루어진  Linked List를 입력 받아, 두 Linked List의 각각의 정수를 합한 값을 다시 Linked List로 반환하는 문제입니다. 각 List는 정수의 revert를 의미합니다. 즉 2->4->3 의 경우 342의 수를 의미합니다. 따라서 5->6->4 에 해당하는 465를 더했을 경우 최종 결과는 807 7->0->8 를 반환해야 합니다. 아래의 그림을 참고 부탁 드립니다.

 

 

 

#LeetCode 2. Add Two Numbers(Solution)

 

이 문제를 풀이는 반복적으로 각 List의 값을 더하고, 그 값이 9을 넘었을 때, carry 변수로 1을 할당하고 다음 Node의 결과 때 각 List의 Node값과 carry의 값을 같이 연산하였습니다. carry의 값은 sum한 결과에 몫을 구하는 연산자(//) 이용하여서 구하였습니다. 아래의 코드를 참조 부탁 드립니다.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


    def _print_all(self):
        while self:
            print(self.val, end=' ')
            self = self.next

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        resultNode = tempNode = ListNode()

        carry = 0
        while l1 or l2 or carry:
            l1_val = 0
            l2_val = 0
            if l1:
                l1_val = l1.val
                l1 = l1.next
            if l2:
                l2_val = l2.val
                l2 = l2.next

            sum = (l1_val +  l2_val + carry)

            new_val = sum % 10
            carry = sum // 10
            tempNode.next = ListNode(new_val)
            tempNode = tempNode.next

        return resultNode.next

 

해당 solution을 아래의 코드로 테스트 하였고, 원하던 대로 결과를 얻는 것을 확인 할 수 있었습니다.

# l1 = [1,2,4], l2 = [1,8,4]
solution = Solution()
L1_3 = ListNode(4)
L1_2 = ListNode(2,L1_3)
L1_1 = ListNode(1,L1_2)

L2_3 = ListNode(4)
L2_2 = ListNode(8,L2_3)
L2_1 = ListNode(1,L2_2)

print("l1 reverse number : ", end=" ")
L1_1._print_all()

print("l2 reverse number : ", end=" ")
L2_1._print_all()

result = solution.addTwoNumbers(L1_1, L2_1)
print("Result reverse number : ", end=" ")
result._print_all()

 

또한 아래와 같이 LeetCode에 제출한 결과는 성공적으로 풀이가 되었음을 확인 하였습니다.

 

방문해 주셔서 감사합니다. 여러분의 공감하기(♥), 댓글과 구독은 저에게 힘이 됩니다.

이상으로 죠쵸였습니다.