Add Two Numbers (Linked List)

LeetCode의 Add Two Numbers 문제다.

Add Two Numbers - LeetCode

연결 리스트로 주어진 역순 숫자들을 각각 합해서 동일하게 역순 숫자들의 연결 리스트로 반환하는 문제다. 이때 리스트의 각 숫자들은 숫자 문자열의 각 자릿수를 역순으로 나열한 것인데 아래와 같은 구조로 주어진다.

https://leetcode.com/problems/add-two-numbers/

예를 들어 [2, 4, 3]의 리스트(연결 리스트지만 일반 리스트로 표현한다)와 [5, 6, 4]의 리스트가 주어지면 [7, 0, 8]의 리스트를 반환해야 하는데 이는 각각 342, 465를 한 글자씩 분리해서 뒤집은 모양이기 때문이다. 그래서 342 + 465 = 807이기 때문에 연결 리스트로 7, 0, 8이 반환되어야 한다. 파이썬에서 생각해볼 수 있는 방법은 연결 리스트의 숫자들을 다 읽어서 원래 수(위의 예제에서는 342, 465)를 만들고 더해서 다시 뒤집어서 각각 노드들로 분리하는 것이다.

 

이를 기반으로 작성한 코드는 다음과 같다.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        num1 = []
        num2 = []
        
        # l1 연결 리스트의 숫자들을 전부 배열에 저장
        while l1:
            num1.append(l1.val)
            l1 = l1.next
        # l2 연결 리스트의 숫자들을 전부 배열에 저장    
        while l2:
            num2.append(l2.val)
            l2 = l2.next
        
        # l1, l2 연결 리스트의 원본 숫자 복구
        sum1 = sum([number * (10 ** index) for index, number in enumerate(num1)])
        sum2 = sum([number * (10 ** index) for index, number in enumerate(num2)])
        addedSum = sum1 + sum2
        
        # 두 수의 합을 기반으로 연결 리스트 생성
        result = None
        previous = None
        # 두 수의 합을 숫자 문자의 배열로 변환 및 반전
        addedSumString = [x for x in str(sum1+sum2)]
        addedSumString.reverse()
        # 각 숫자 문자로 연결 리스트의 노드 구축
        for character in addedSumString:
            current = ListNode()
            # 첫번째 노드 설정
            if result is None:
                result = current
            current.val = int(character)
            # 두 번째 노드부터 이전 노드가 현재 노드를 연결
            if previous:
                previous.next = current
            previous = current
        
        # 첫번째 노드 반환
        return result

하지만 이런 방식은 불필요한 연산이 너무 많다. 당장 맨 처음부터 두 연결 리스트의 모든 노드들을 읽어서 배열에 저장해 두고 List Comprehension을 이용해 배열에 있는 숫자들로 원래 숫자를 구성하고 있다. 그리고 이 두 수를 합해서 다시 문자열로 변환하여 문자로 분리하고 나중에 다시 정수로 변환하여 연결 리스트에 합하고 있다. 불필요한 연산이 많고 연결 리스트의 특성을 이용한 풀이도 아니기 때문에 좀 다른 방법을 생각해 볼 필요가 있다.

생각해볼 수 있는 다른 방법은 각 숫자끼리 더해서 자리올림을 구현하는 것이다. 위의 연결 리스트에서는 2 -> 4 -> 3, 5 -> 6-> 4로 1의 자리 숫자부터 하나씩 주어지고 있다. 같은 자리 숫자끼리 더해서 10 이상이면 다음 연산에 자리올림을 추가하고 합에서 10을 빼는 방식으로 구현하면 두 연결 리스트를 탐색하는 것만으로 두 수의 합을 구하고 연결 리스트도 구축할 수 있을 것이다.

 

이를 기반으로 작성한 코드는 다음과 같다.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    	# 첫번째 노드를 가리키는 result 변수
        result = None
        # 현재 노드를 가리키는 이전 노드를 저장하는 previous 변수 
        previous = None
        # 자리올림 값
        carry = 0
        
        # l1, l2 연결 리스트에 아직 숫자가 남아있거나 자리올림 값이 남아있는 동안 반복
        while l1 or l2 or carry:
            # 자리올림 값, l1, l2 연결 리스트의 숫자를 nodeSum에 합산
            nodeSum = carry
            if l1:
                nodeSum += l1.val
            if l2:
                nodeSum += l2.val
            
            # 만약 자리올림이 발생했다면 nodeSum에서 10을 빼고 자리올림 변수를 1로 설정.
            # 그렇지 않다면 0으로 초기화.
            if nodeSum > 9:
                carry = 1
                nodeSum -= 10
            else:
                carry = 0
            
            # 현재 자릿수의 합을 저장할 연결 리스트의 노드 생성
            current = ListNode()            
            current.val = nodeSum
            # 첫번째 노드인 경우 result 변수에 할당
            if result is None:
                result = current
            # 두 번째 이후 노드인 경우 이전 노드가 현재 노드를 가리키도록 설정
            if previous:
                previous.next = current
                
            # l1, l2 리스트는 다음 숫자로 이동 및 현재 노드를 이전 노드로 설정   
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
            previous = current
        
        # 첫번째 노드 반환
        return result

자리올림 값을 유지하기 위해 carry라는 변수를 추가적으로 사용하는 것을 볼 수 있다. 그리고 l1, l2 연결 리스트가 비대칭, 즉 서로 다른 길이일 뿐 아니라 마지막 숫자까지 계산한 후에도 자리올림 값이 남아있을 경우를 대비해서 while 조건문을 'l1 or l2 or carry'처럼 설정한 것에 유의하자. 파이썬에서 정수 변수는 조건문에서 0일 경우 False, 그 외의 경우 True로 취급된다.

 

 

2번 문제인데 바로 Medium 단계라 좀 난감할 수도 있지만 단방향 연결 리스트와 자리올림을 잘 활용하면 어렵지 않게 풀 수 있다.