[알고리즘] - 링크드리스트 합 계산

문제

Q.  다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오. 

예를 들어 아래와 같은 링크드 리스트를 입력받았다면,
각각 678, 354 이므로 두개의 총합
678 + 354 = 1032 를 반환해야 한다.

단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.

[6] -> [7] -> [8]
[3] -> [5] -> [4]

 

정답 풀이

각 링크드 리스트의 헤드를 따라가면서, 자릿수에 맞게 더해주면 된다. 자릿수에 맞게 더하기 위해서는 총액에서 10을 곱한 다음에 현재 노드의 값을 더해주면 된다.

현재 [6] → [7] → [8] 로 연결되어 있으니까 sum 이라는 변수에 0 을 저장한 다음에, 0 * 10 + 6 을 하면 sum 은 6이 된다.

그리고 6 * 10 + 7 을 하면 sum 은 67 이 되고, 67 * 10 + 8 을 하면 sum 이 678 이 되어 값을 구할 수 있다.

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

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = 0
    cur_1 = linked_list_1.head
    while cur_1 is not None:
        sum_1 = sum_1 * 10 + cur_1.data
        cur_1 = cur_1.next
        
    sum_2 = 0
    cur_2 = linked_list_2.head
    while cur_2 is not None:
        sum_2 = sum_2 * 10 + sum_2.data
        cur_2 = cur_2.next
    
    return sum_1 + sum_2

linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)

print(get_linked_list_sum(linked_list_1, linked_list_2))

 

그런데 중복된 코드가 너무 많고, 링크드 리스트가 추가될 경우 모든 코드를 입력해야 한다는 단점이 있다. 이럴 때는 함수로 추출해주면 코드의 간결성이 더 높아지고 유지보수성이 더 좋아진다.

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

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

def get_single_linked_list_sum(linked_list):
    sum = 0
    cur = linked_list.head
    while cur is not None:
        sum = sum * 10 + cur.data
        cur = cur.next
        
    return sum

def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = get_single_linked_list_sum(linked_list_1)
    sum_2 = get_single_linked_list_sum(linked_list_2)

    return sum_1 + sum_2

linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)

print(get_linked_list_sum(linked_list_1, linked_list_2))

문제를 풀고 알게 된 개념 및 소감

• 코드를 다 작성하더라도 중복된 코드들이 많으면 함수로 추출하자.