정글사관학교 41일차 TIL: 두 수의 덧셈(Leetcode #2: add-two-numbers)

오늘은 밖에서 오래 있느라 제대로 정리를 못했..알고리즘 문제 푼 걸 정리하고 빠르게 마무리. 문제 링크는 여기.

 

연결 리스트 개념은 잘 안다고 생각했는데 파이썬 클래스로 구현하는 방식이 손에 잘 익지 않더라. 클래스에서 어떻게 구현했는지 빠르게 보자.

 

주어진 연결리스트 클래스를 구현하는 ListNode는 클래스를 구성하는 원소가 두 가지인데, val과 next이다.

 

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

연결 리스트에서 해당 노드의 값을 val, 다음 연결 리스트를 next에 저장한다. 이때, self.next에 들어가는 것은 다음 노드의 값이 아니라 현재 연결 리스트의 노드 헤드를 제외한 나머지 연결리스트가 통째로 들어간다. 즉, 위의 연결 리스트는 재귀로 구성되어 있다는 점이 포인트. 이게 직관적으로 잘 와닿지 않아서 많이 헷갈렸다. (C에서는 포인터를 쓰는데 파이썬에서는 연결 리스트를 통으로 저장하니 원..)

 

1차적으로 생각했던 풀이는 연결 리스트를 뒤집고 리스트 값을 일일이 빼와서 더한다음 다시 연결리스트로 만드는 것인데..책에서도 이 풀이를 소개하나 좋은 풀이는 아니라고 하는 게 함정. 근데 문제는 뒤에 소개하는 풀이는 더 모르겠다..일단 이거라도 정리.

 

먼저 리스트부터 뒤집어보자. 앞의 리스트와 뒷 리스트 위치를 바꿔가며 최종적으로 뒤집은 연결 리스트를 반환한다.

def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
            
        return prev

 

그 다음은 연결 리스트를 해제해 파이썬 리스트로 바꾼다.

 

def toList(self, node: ListNode) -> List:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list

 이후에는 이를 다시 연결 리스트로 바꾸는 함수도 만들어보자.

 

def toReversedLinkedList(self, result: str) ->ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node

이제 마지막, 주어진 함수 addTwoNumbers에서 두 연결 리스트를 파이썬 리스트로 바꿔 더한 다음, 다시 연결 리스트로 바꾸는 작업을 수행하게 한다.

 

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))
        
        resultStr= int("".join(str(e) for e in a)) + int("".join(str(e) for e in b)) 
            
        return self.toReversedLinkedList(str(resultStr))

 

최종 코드는 아래와 같다.

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
            
        return prev
    def toList(self, node: ListNode) -> List:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        return list
    
    def toReversedLinkedList(self, result: str) ->ListNode:
        prev: ListNode = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node
    
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        a = self.toList(self.reverseList(l1))
        b = self.toList(self.reverseList(l2))
        
        resultStr= int("".join(str(e) for e in a)) + int("".join(str(e) for e in b)) 
            
        return self.toReversedLinkedList(str(resultStr))