✚ Add two numbers

리트코드 2번 Add two numbers 풀이 과정

Add two numbers

• 뒤집어서 주어진 2개의 연결리스트를 더해서 다시 연결리스트로 반환하라는 문제이다.
  자세히 설명하자면 뒤집어서 주어진 연결리스트를 정상적인수로 반환해서 더하고 그값을 다시 뒤집어서 반환해야한다.

풀이 과정

• 처음에 생각한 방법은 각 자리수를 더해서 자리올림이 발생하면 다음자리에 1을 추가하는 방식으로 구현하려고 했는데 아이디어만 떠오르고 구현하는법을 모르겠어서 무식하게 하기로 했다.

생각한 방법

1. 연결리스트를 리스트로 변환한다.
2. 변환된 리스트를 뒤집고 정수로 바꿔서 더한다.
3. 다시 문자열로 바꿔서 각 숫자를 띄어서 리스트로 변환하고
4. 변환된 값으로 연결리스트를 만든다.

• 3번까지는 야무지게 진행했는데 4번 리스트를 연결리스트로 바꾸는 법을 모르겠어서 실패했다....

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        list1 = []
        list2 = []
        while l1 and l2:
            list1.append(str(l1.val))
            l1 = l1.next
            list2.append(str(l2.val))
            l2 = l2.next
        list1.reverse()
        list2.reverse()
        list1 = int(''.join(list1))
        list2 = int(''.join(list2))
        list3 = list(str(list1 + list2))
        list3.reverse()
        list3 = list(int(i) for i in list3) 
        return list3

보면은 3번 리스트까지 만들었는데 연결리스트변환 구현법을 몰라서 막혔다.

상길선생님의 풀이

• 상길 선생님의 첫번째 풀이에서는 나와 비슷한 로직으로 구현하셨다.
  그렇지만 선생님은 각 기능을 함수로 만드셨다.

# 상길선생님의 풀이 
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: ListNode, l2: ListNode) -> 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))

• 각 기능을 깔끔하게 함수로 만들어서 내 코드같이 중복이 없다.
• 연결리스트로 뒤집어서 변환하는 기능을 구현하는법을 알게됐다.
• 연결리스트를 만들기 뒤집기등의 문제를 직접 풀었으면 이 문제는 맞혔을거란 생각이 들어서 기존에 안푼 연결리스트 뒤집기나 연결리스트 변환 문제를 풀어봐야겠다.

전가산기 구현

• 내가 처음 생각한 아이디어 방식으로 푸는 풀이방법이다.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = head = ListNode(0)

        carry = 0 #자릴수 올림수 
        while l1 or l2 or carry: # l1 or l2 or carry 셋 중 하나라도 안비었으면 계속 ㄱ 
            sum = 0
            # 두 입력값의 합 계산 
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2: 
                sum = l2.val
                l2 = l2.next
            
            # 몫(자리올림수)과 나머지(값) 계산
            carry, val = divmod(sum + carry, 10)
            head.next = ListNode(val)
            head = head.next
    
        return root.next

• 정말 구현을 이리 잘할까 싶은 풀이 방법이었다.
• 리턴값으로 root.text를 하는 방식을 취한 부분에서 놀랐다.

divmod함수

• 원래 알고 있었던 함수지만 필요할 때 생각이 안난다.

a = divmod(10,3)
print(a)
>>> (3, 1)

나누는 수와 나눌 수 를 쥐어주면 몫과 나머지를 튜플로 반환한다. 

• 아이디어를 구현하는 방법을 더 연습해야겠다.