[python] LeetCode 2번: Add Two Numbers(medium)

in Algorithm on LeetCode
[python] LeetCode 2번: Add Two Numbers(medium)

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

cf) 조건 중에 leading zero가 없다는 말은 32가 아니라 0032 같이 숫자 앞에 의미 없는 0이 붙어 있지 않다는 뜻이다.

음수가 아닌 정수를 가지고 빈 경우가 없는 연결 리스트가 두 개 주어진다. 숫자들은 역순으로 저장되고, 각각의 노드는 한 개의 숫자를 가진다. 두 연결리스트의 숫자들을 더한 값을 연결리스트의 형태로 반환하라.

문제 링크 : 리트코드 2번

<Try>

갑자기 연결리스트가 등장하여 괜히 어렵게 느껴질 수 있겠지만 조금만 들여다보면 이 문제의 제목인 “Add Two Numbers”처럼 그냥 두 숫자를 더하는 문제임을 알 수 있다. 문제에서 주어진 예시는 다음과 같다.

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

각각의 연결리스트들이 표현하는 숫자는 342, 465 이다. 이 두 개의 숫자를 더한 값인 807을 연결리스트 형태인 [7, 0, 8]으로 반환하는 것이 목적이다.

아직 리트코드 문제 형식이 익숙치 않아 위에 표현된 연결리스트 형태가 int 인자를 담은 리스트로 보여 처음에 혼돈이 왔지만, 문제를 풀고 확인한 결과 연결리스트의 첫 원소인 7을 담은 ListNode 객체를 반환시키면 된다. 뒤에 0, 8 값은 next로 연결되어 있는데 알아서 반환해준다.

처음 시도는 위에 설명한 덧셈 원리로 접근하였다.

  1. [2, 4, 3], [5, 6, 4]를 각각 342, 465로 변환
  2. 두 숫자의 합인 807을 다시 연결리스트 형태인 [7, 0, 8]로 변환

결과적으로 Accepted 됐으나, 효율적인 코드도 아니고 이 문제를 낸 취지와 맞지 않는 것 같아서 연결리스트 형태 그대로 문제를 다시 풀어 보았다.


<Solution>

# 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: ListNode, l2: ListNode) -> ListNode:
        currNode1 = l1
        currNode2 = l2
        # 두 숫자를 더한 값이 10을 넘으면 carry = 1, 아니면 0
        carry = 0
        # dummyHead: 반환할 결과값을 담을 객체 그릇
        dummyHead = ListNode()
        output = dummyHead
        while True:
            if currNode1 or currNode2:
                v1 = currNode1.val if currNode1 else 0
                v2 = currNode2.val if currNode2 else 0
                rest = (v1 + v2 + carry) % 10
                carry = (v1 + v2 + carry) // 10
                output.next = ListNode(rest)
                
                output = output.next
                if currNode1:
                    currNode1 = currNode1.next
                if currNode2:
                    currNode2 = currNode2.next
                
            else:
                #마지막 덧셈 후 결과값이 10을 넘겼을 때. ex) 18 + 82 = 100
                if carry == 1:
                    output.next = ListNode(1)
                break
        
        return dummyHead.next

이 코드의 경우 최대 l1과 l2 중 더 긴 리스트의 길이를 n이라 할때, 시간 복잡도는 O(n)이다.

파이썬 언어에서 객체의 깊은 복사, 얕은 복사에 대해 생각해 볼 수 있는 문제였던 것 같다.

© 2020. All rights reserved.