파이썬 알고리즘 - 두 링크드리스트(LinkedList)의 합(SUM) 계산

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(9)

 

(1). 개발자 면접 트레이닝 - 두 개의 링크드리스트(LinkedList)의 합(SUM) 계산

① 단순해 보이지만, 난이도가 있는 알고리즘 문제

② 두 링크드리스트의 각 자리수를 계산하는 것이 중요

③ 합산 된 링크드리스트의 합을 리턴

④ 예를들어 [7, 1, 6]  +  [5, 9, 2] 두 링크드리스트의 합 -> 912  출력

 

 

(2). 소스 코드

PYTHON

#sum_linkedlist.py
import unittest

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

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

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

    def getHead(self):
        return self.head

    def printlist(self):
        cur = self.head
        res = []
        while cur is not None:
            res.append(cur.val)
            cur = cur.next
        return str(res)

def solution(list1, list2):
    v1 = list1.getHead()
    v2 = list2.getHead()
    carry = 0
    while v1 is not None:
        val = ((v1.val + v2.val) % 10) + carry
        carry = (v1.val + v2.val) // 10
        v1.val = val
        v1 = v1.next
        v2 = v2.next

    cur = list1.getHead()
    val = 0
    mul = 1
    while cur is not None:
        val = val + (cur.val * mul)
        mul = mul * 10
        cur = cur.next
    return val

class LinkedListTest(unittest.TestCase):
    def test(self):
        list1 = LinkedList(7)
        list1.add(1)
        list1.add(6)

        list2 = LinkedList(5)
        list2.add(9)
        list2.add(2)

        self.assertEqual(912, solution(list1,list2))

unittest.main()

 

(3). 소스 코드 분석

① 14 라인 : 헤드(Head) 노드 선언

② 24 라인 : 현재 링크드리스트(LinkedList)의 헤드 반환 함수 선언

③ 36 라인 : 두 링크드리스트의 합 위한 Soluteion 메소드 선언

④ 43 라인 : 10으로 나누어 몫을 계산 몫을 계산

⑤ 55 라인 : 자리수에 10을 곱해 각 자리수 단위 작성 구간

⑥ 61 ~ 끝 : 링크드리스트(LinkedList) 선언 및 assertEqula 단위 테스트 함수를 사용하여 입력 결과와 출력결과를 비교

LinkedList(링크드리스트) 관련 알고리즘 문제는 자주 활용, 출제 되므로 Java, C  등으로 작성해보자.

 

참고로 이 예제는 위에서 언급했다시피, 난이도가 상승된 알고리즘이라 볼 수 있다.

(4). 실행결과1 - 단위테스트 정상 출력(합산 결과 같을 경우)

 

 

(5). 실행결과2 - 단위테스트 에러 출력(합산 다를 경우)