2.5 리스트의 합

문제 

연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 즉 첫번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와같은 방식으로 표현된 숫자 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라.

 

예제 

입력 (7->1->6) +(5-> 9-> 2) 

출력 ( 2->1-> 9) 

=> 617 + 295 = 912 

 

연관문제

각 자릿수가 정상적으로 배열된다고 가정하고 같은 문제를 풀어보자

 

예제 

입력 (6->1->7) +( 2->9->5) 

출력 ( 9->1->2) 

=> 617 + 295 = 912 

 

해결법

기본 문제는 우리가 덧셈을 하듯이 더한 숫자의 1의 자리 숫자로 노드를 만들고 캐리를 넘김으로써 재귀적으로 해결할 수있다.

class Node:
    def __init__(self, dataval=None):
        self.data = dataval
        self.next = None


def Solution(l1, l2):
    result = add_list(l1,l2,0)
    return result

def add_list(l1,l2,carry):
    if (l1 is None and l2 is None and carry == 0):
        return None
    
    value = carry
    value += l1.data if l1 is not None else 0
    value += l2.data if l2 is not None else 0

    new_node = Node(value%10)
    
    next_node = add_list(l1.next if l1 is not None else None
                         , l2.next if l2 is not None else None
                         , 1 if value >=10 else 0)
    new_node.next = next_node
    
    return new_node

 

연관문제의 해결법

연관문제는 재귀를 사용하고 자릿수를 넘긴다는 점에서 개념적으로는 같지만, 구현하려고 했을때 까다로운 부분들이 있다.

1. 한 리스트가 다른 리스트보다 짧은 경우를 처리해야한다. -> 이 경우는 짧은 리스트 앞쪽에 0을 채워 넣음으로써 해결할 수있다.

2. 이전에서는 계산결과를 꼬리쪽에 붙여나갔지만 이제는 계산결과를 머리쪽에 붙여 나가야하기 때문에 재귀 호출시 만들어진 리스트 결과물 뿐만아니라 carry까지 넘겨야한다.  -> 이부분은 새로운 class를 생성함으로써 해결할 수있다.

 

class partialSum:
    def __init__(self, sum_node = None)
        sum_node = None
        carry = 0

def length(l):
    cnt = 0
    while l is not None:
        cnt +=1
    return cnt

def insertbefore(node, data):
    new_node = Node(data)
    new_node.next = node if node is not None else None
    return new_node

def padding(node, cnt):
    while cnt >0 :
        node = insertbefore(node, 0)
        cnt -= 1
    return node

def make_sum(l1, l2):
    if l1 is None and l2 is None:
        return partialSum(0)

    sum = make_sum(l1.next, l2.next)
    value = sum.carry + l1.data + l2.data
    sum.sum_node = insertbefore(sum.sum_node, value%10)
    sum.carry = 1 if value >= 10 else 0

    return sum

def Solution(l1, l2):
    len_l1 = length(l1)
    len_l2 = length(l2)
    if len_l1 < len_l2 :
        l1 = padding(l1, len_l2 - len_l1)
    elif len_l1 > len_l2 :
        l2 = padding(l2, len_l1- len_l2)

    sum = make_sum(l1, l2)
    if sum.carry > 0 :
        return insertbefore(sum.sum_node, sum.carry)
    else
        return sum.sum_node