[LeetCode] 2번 Add Two Numbers 문제 풀이 (파이썬)

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

Add Two Numbers - LeetCode

아주 간단한 링크드 리스트 문제인데, 나는 링크드 리스트에 대한 개념 정도만 있지 실제로 구현해서 문제풀이에 사용해본 경험은 거의 없었기 때문에 이 문제로도 꽤나 많은 오류를 거쳤다.

애초에 문제 자체는 연결 리스트를 숫자로 바꿔서 더한 후 다시 연결 리스트로 바꾸라는 의도는 아니었던 것 같으나, 나는 링크드 리스트 구현을 해보는 것이 목적이었기 때문에 그냥 저 방법대로 했다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        # 연결 리스트를 숫자로 바꿔주는 함수
        def l_to_n(list_node):
            s = ""
            while list_node:
                s += str(list_node.val)
                list_node = list_node.next
            return int(s[::-1])
        
        # 숫자를 (거꾸로 된) 연결 리스트로 바꿔주는 함수
        def n_to_l(num):
            # 숫자를 문자열화하여 순서를 거꾸로 바꾼 후 이를 다시 숫자로 바꿔 리스트화해줌
            n_reverse = list(map(int, str(num)[::-1]))
            list_node = ListNode() # 리턴할 연결 리스트 초기화 (첫 번째 노드)
            now = list_node # list_node는 그대로 두고 뒤로 next들을 추가해줄 것이기 때문에 현재 노드를 가리키는 변수(가변하는) 따로 필요
            # 첫 번째 노드는 디폴트 상태(val = 0)로 두고 해당 노드 뒤로 숫자들 연결해주기
            for n in n_reverse:
                now.next = ListNode(val = n) # 새로운 리스트 노드 생성해주되, 생성시 val에 바로 n 대입
                now = now.next # n_reverse의 모든 원소를 다 iterate 한 후에는 마지막 원소의 next가 None인 상태로 종료
            return list_node.next
            
        return n_to_l(l_to_n(l1) + l_to_n(l2))

두 번째 함수를 짜다가 연결 리스트에 대한 이해 부족으로 막히는 부분이 꽤 나와서, 다른 분의 코드를 참고하여 작성하였다.

참고 코드: https://life-of-erin.tistory.com/29

[LeetCode 리트코드] Add Two Numbers, python 파이썬

 

---

추가 풀이

연결 리스트 상태에서 푸는 방식을 적용해 봤는데, 연결 리스트에 대한 완벽하지 못한 숙지 때문인지 오류가 굉장히 많이 나서 정말 인내심에 한계가 여러 번 왔으나, 상길북의 도움을 받아 코드를 조금씩 뜯어고치면서 결국 성공했다.

처음 적어낸 풀이는 굉장히 길고 중복이 많다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        # 왜인지 확실하지는 않지만, 아마도 head는 계속 next로 이어지면서 변하는 값인 반면 node는 고정된 시작점이기 때문에? node와 head를 전부 선언해주고 시작해야 한다.
        node = head = ListNode(0)
        extra = 0 # 더했을 때 10이 넘어가면 다음 자리로 올리기 위한 변수
        
        while l1 and l2:
            # 10으로 나눈 나머지와 몫이 각각 extra와 새 노드(head)의 val이 된다.
            extra, val = divmod((l1.val + l2.val + extra), 10)
            l1 = l1.next
            l2 = l2.next
            
            # 이하 두 줄은 사실 아직 이해가 완전히 가지 않는다.
            # extra, val 대신 extra, head.val이라고 한 후 아래서 head = head.next라고 하면 NoneType에는 val, next가 없다는 오류가 뜬다.
            # 이미 생성된 ListNode의 val을 바꿔줄 수는 없는 것일까? 아직 잘 모르겠음.
            # 하여튼 그래서 상길북에서 힌트를 얻어 head에 바로 val을 대입해주는 대신 val을 val로 갖는 새로운 ListNode를 생성한 후 head.next로 이어주었다.
            head.next = ListNode(val)
            head = head.next
        
        while l1:
            extra, val = divmod((l1.val + extra), 10)
            l1 = l1.next
            head.next = ListNode(val)
            head = head.next
            
        while l2:
            extra, val = divmod((l2.val + extra), 10)
            l2 = l2.next
            head.next = ListNode(val)
            head = head.next
            
        while extra:
            extra, val = divmod(extra, 10)
            head.next = ListNode(val)
            head = head.next
            
        return node.next

너무 중복된 부분이 많아 조금 깔끔하게 만들기 위해 코드를 나름대로 리팩토링했다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        node = head = ListNode(0)
        extra = 0
        
        # 수많은 while문을 하나로 줄였다.
        while l1 or l2 or extra:
            # divmod에는 l1.val, l2.val, extra 등이 그때그때 상황에 따라 들어간다. 그걸 sum에 더해줄 것
            sum = 0
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
            if extra:
                sum += extra
                
            # while문 안이라는 것을 잊지 말 것
            extra, val = divmod(sum, 10)
            head.next = ListNode(val)
            head = head.next
            
        return node.next