[리트코드] Add Two Numbers(python)

리트코드, Add Two Numbers_두 수 더하기

 

TL;DR

• 연결 리스트(Linked List) 문제를 해결할 수 있는지

문제 분석

1. 음수가 아닌 정수를 표현하는 비어 있지 않은 두 개의 연결 리스트가 주어진다.
2. 숫자들은 연결 리스트에 거꾸로 삽입되어 있고, 각 노드는 자리수를 포함하고 있다.
3. 두 숫자를 더한 결과를 링크드 리스트에 담아 반환한다.
4. 0 하나만 있는 것을 제외하고 0으로 시작하는 경우는 없다.

 

- 1 ~ 4 : 해결해야 하는 문제 조건에 대해서 설명하고 있다. 두 개의 숫자가 역으로 연결 리스트에 저장되어 있다는 것에 주목해야 한다.

입출력 형태

입출력 예시

 

- 예시 1

    - L1이 나타내는 수는 342, L2가 나타내는 수는 465이다.

    - 두 수를 더한 결과인 807을 연결 리스트에 역으로 저장한 것을 반환하면 된다.

풀이

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        rev_l1, rev_l2 = None, None
        l1_head, l2_head = l1, l2
        num1, num2 = 0, 0
        num1_s, num2_s = '', ''
        
        # 1. 주어진 연결 리스트를 역으로 만들기
        while l1:
            rev_l1, rev_l1.next, l1 = l1, rev_l1, l1.next
        while l2:
            rev_l2, rev_l2.next, l2 = l2, rev_l2, l2.next
            
        # 2. 연결 리스트를 숫자로 만들어 덧셈 진행하기
        while rev_l1:
            num1_s += str(rev_l1.val)
            rev_l1 = rev_l1.next
        while rev_l2:
            num2_s += str(rev_l2.val)
            rev_l2 = rev_l2.next
         
        for i, s in enumerate(num1_s):
            num1 += int(s) * 10 ** (len(num1_s) - 1 - i)
        for i, s in enumerate(num2_s):
            num2 += int(s) * 10 ** (len(num2_s) - 1 - i)  
        result = num1 + num2

        # 3. 합을 연결 리스트에 넣고 역으로 만들어 반환하기
        answer = None
        for i in range(len(str(result)) - 1, -1, -1):
            tmp = ListNode()
            tmp.val = int(str(result)[i])
            tmp.next = answer
            answer = tmp
            
        a = answer
        rev_a = None
        while answer:
            rev_a, rev_a.next, answer = answer, rev_a, answer.next
            
        return rev_a

 

- 가장 처음에 푼 풀이 방법이다.

- 매우 단순하게 주어진 연결 리스트를 반대로 뒤집어 나타내는 숫자와 같은 배열로 변경하고

- 뒤집은 연결 리스트로 숫자를 만들어 덧셈을 진행한다. 그 이후

- 덧셈의 결과를 연결 리스트에 역으로 집어넣는 것을 구현한 코드이다.

- 하지만 중복되는 코드가 매우 많고, 굉장히 보기 좋지 않다. 따라서, 문제를 다 풀고 난 이후 코드를 개선하였다.

개선한 풀이

class Solution:
    def makeDigits(self, rev_linked_list: ListNode) -> int:
        str_digits, digits = '', 0
        
        while rev_linked_list:
            str_digits += str(rev_linked_list.val)
            rev_linked_list = rev_linked_list.next
            
        for i, s in enumerate(str_digits):
            digits += int(s) * 10 ** i
            
        return digits
    
    def makeLinkedList(self, target_num: int) -> ListNode:
        linked_list = None
        for i in range(len(str(target_num))):
            post = ListNode()
            post.val, post.next = int(str(target_num)[i]), linked_list
            linked_list = post
        return linked_list
    
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        answer = None
        num1, num2, sum_results = 0, 0, 0
        
        num1, num2 = self.makeDigits(l1), self.makeDigits(l2)
        result = num1 + num2
        
        answer = self.makeLinkedList(result)
        return answer

 

- 처음 작성한 코드를 개선한 코드이다. 처음 작성한 코드의 중복되는 부분을 모두 함수로 바꾸어 작성하였다.

- 그리고 연결 리스트를 뒤집는 부분을 삭제하였다. 연결 리스트를 뒤집을 필요 없이 연결 리스트를 조회하며 값을 쌓아가면, 원래 나타내는 숫자를 얻어낼 수 있기 때문이다.

- 그렇게 하여 주어진 연결 리스트를 숫자로 만드는 makeDigits 함수와 얻어낸 답을 연결 리스트로 만드는 makeLinkedList 함수를 통해 코드를 개선하였다.

- 시간 복잡도는 오히려 증가하였지만, 공간 복잡도를 감소시킬 수 있었다.