LeetCode: Add Two Numbers

 

 

 

오늘은 leetcode문제를 리뷰해보려고 한다. 

 

이 문제는 linked list를 사용해서 덧셈연산을 하는 문제이다.

 

나는 제출형식을 맞추는 것에 애를 먹었다.

 

문제에서는 linked list를 만드는 ListNode class가 있다고 가정한 다음 문제를 풀기 시작한다.

 

그리고 링크드 리스트를 받은 다음 합의 링크드 리스트를 만들어서 return해주면 된다.

 

나는 문제의 입력과 출력형식의 맞춰서 linked list와 list를 변환하는 함수까지 짜버렸다.

 

풀이방식은 간단하다.

 

1. 링크드 리스트의 값이 존재할때까지 while로 이동하면서 값을 더해준다.

 

2. while문 안에서 덧셈의 결과가 10이 넘는다면 다음 자리수를 carry변수에 저장하여 함께 더해준다.

 -> //10 연산자를 사용하여 carry를 구해줌

 

3. 덧셈의 결과를 ListNode 의 val로 저장해준다.

 -> val을 할당한 뒤에 ListNode 생성자를 호출하고 current를 current.next로 옮겨 다음 링크드리스트로 이동한다. 

 

4. ListNode의 첫 주소(dummy.next)를 반환한다.

 

 

Local용과 제출용 두가지 코드 다 올리겠다.

 

 

---

Local용 코드

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    
def list_to_linkedlist(lst):
        dummy = ListNode()
        current = dummy
        for val in lst:
            current.next = ListNode(val)
            current = current.next

        return dummy.next
    
def linkedlist_to_list(dummy):
        lst = []
        while dummy:
            lst.append(dummy.val)
            dummy = dummy.next
        
        return lst
            
class solution(object):
    def addTwoNumbers(self, l1, l2):
        l1 = list_to_linkedlist(l1)
        l2 = list_to_linkedlist(l2)

        dummy = ListNode()
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            temp = val1 + val2 + carry

            carry = temp // 10
            temp = temp % 10

            current.next = ListNode(temp)
            current = current.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        res = linkedlist_to_list(dummy.next)

        return res

l1 = [2, 4, 3]
l2 = [5, 6, 4]

sol = solution()
res = sol.addTwoNumbers(l1, l2)
print(res)

 

제출용 코드

# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

            
class Solution(object):
    def addTwoNumbers(self, l1, l2):

        dummy = ListNode()
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            temp = val1 + val2 + carry

            carry = temp // 10
            temp = temp % 10

            current.next = ListNode(temp)
            current = current.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummy.next