16. Add Two Numbers

리트코드

• 역순으로 저장된 연결 리스트의 숫자를 더하라

1. 자료형 변환 (76ms)

# 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) -> ListNode:
        list: List = []
        while node:
            list.append(node.val)
            node = node.next
        
        return list
        
    #파이썬 리스트를 연결 리스트로 변환
    
    def toReversedLinkedList(self, result: ListNode) -> 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))

• 먼저, 역순으로 된 연결리스트를 뒤집어야 한다.

  • 반복을 통해 뒤집는다

• 다음으로 덧셈 연산을 위해 연결 리스트를 파이썬의 리스트로 변경한다.

  • 위 코드는 node를 반복하며 값을 리스트에 추가하는 함수를 사용하였다.

• 리스트를 다시 연결 리스트로 변경한다.

  • 여기서는 순서대로 엮어 나가는 방식으로 구현했는데, 이렇게 하면 뒤집힌 연결 리스트가 된다.

  • 이 문제에서는 출력 또한 역순으로 하도록 요구하고 있기에 이 상태 그대로 내보내면 된다.

  • 다시 뒤집어야 한다면 위의 함수에 다시 대입하면 된다.

• 이제 덧셈 연산을 하면 되는데, 이를 위해서는 리스트를 int 형태로 결합해야 한다.

  • 이전에 문자열 리스트를 str으로 면경하는 과정을 살펴본 바 있다.

    ''.join(s)와 같은 형식으로 처리가 가능하다.

  • 여기서는 str(e)로 각 항목을 문자로 변경한 다음 join()으로 합쳤다.

  • 또한 , 덧셈 연산을 위해서 int로 다시 변경해주어야 한다.

  
        resultStr = int(''.join(str(e) for e in a)) + \
                    int(''.join(str(e) for e in b)) 

• 마지막으로, 최종 계산 결과를 연결 리스트로 바꿔준다.

  • toReversedLinkedList()를 사용하면 쉽게 변환할 수 있다.

  • 단, 여기서는 문자열을 입력값으로 받기 때문에 다음과 같이 str()으로 한 번 변환하는 작업이 필요하다

	return self.toReversedLinkedList(str(resultStr))

2. 전가산기 구현 (88ms)

논리 회로의 전가산기(Full Adder)과 유사한 형태를 구현해보자

• 이진법이 아니라 십진법이라는 차이만 있을 뿐, 자리 올림수(Carry)를 구하는 것까지 가산기의 원리와 거의 동일하다.

<전가산기 진리표(Truth Table)>

• 입력값 A와 B, 이전의 자리올림스(Carry in) 이렇게 3가지 입력으로 합(Sum)과 다음 자리올림수(Carry out) 여부를 결정한다.

<전가산기 회로도>

• 입력값 A, B는 오른쪽으로는 XOR 게이트를 통과한 결과가 나아가고, 아래로는 AND 게이트를 통과한 결과가 나아간다.

• 그렇게 함과 다음 자리올리수 위치에 도달한 결과가 진리표이다.

• 실제로 덧셈연산을 수행하는 논리회로의 원리며, 산술 논리 장치(Arithmetic Logic Unit)를 구성하는 디지털 회로의 일부분이다.

  • 산술 논리 장치는 컴퓨터의 중앙 처리 장치, 그러니까 우리가 잘 아는 CPU의 한 부분이기도 하다.

# 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:ListNode, l2:ListNode) -> ListNode:
        
        root = head = ListNode(0)
        
        carry = 0
        
        while l1 or l1 or carry:
            sum = 0
            
            #두 입력값의 합 계산
            
            if l1:
                sum += l1.val
                l1 = l1.next
                
            if l2:
                sum += l2.val
                l2 = l2.next
                
            # 몫(자리올림수)과 나머지(값) 계산
            # carry = sum + carry // 10
            # val = sum + carry % 10
            carry, val = divmod(sum + carry, 10)
            
            head.next = ListNode(val)
            head = head.next
            
        return root.next

• 연산 결과로 나머지(Remainder) 를 취하고 몫(Quotient) 은 자리 올림수 형태로 올리는 전가산기의 전체적인 구조만 참고해 풀이한다.

• l1, l2는 전가산기 회로도에서 A, B의 역할과 동일하다. 두 입력값의 연산을 수행하고 다음과 같이 자릿수가 넘어갈 경우에는 자리 올리수를 설정할 것이다.

  carry, val = divmod(sum + carry, 10)

• divmod( )는 파이썬의 내장 함수로, 몫과 나머지로 구성된 튜플을 리턴한다.

  • 즉, (a//b, a%b)와 동일한 결과를 출력한다.

• divmod의 결과로, 가산 결과가 두 자릿수가 될 경우, 몫은 자리올림수로 설정해 다음번 연산에 사용되게 하고, 나머지는 값으로 취한다.

• 다음으로 이 값을 연결 리스트로 만들어주면 된다.

• 원래 가산기는 논리 회로를 이용해 이진 연산을 수행하지만 여기서는 전체적인 구조만 참고하여 십진 연산에 응용해봤다.