[LeetCode 리트코드] Add Two Numbers - python

이번에 풀 문제는 Add Two Numbers이다.

문제

그니까 두 수가 링크드 리스트 두 개로 주어지는데 거꾸로 주어진다.
이 링크드 리스트 두개를 사용해서 두 수를 더하면 된다.
그러면 거꾸로 된 합이 나온다.

예시에서 2->4->3 은 숫자로 따지면 342고 5->6->4는 465이다.
이걸 거꾸로된 링크드 리스트를 이용해서 더해보라는 거다.
원래 342+465 = 807이지만 거꾸로 구했으니 7->0->8을 리턴하면 된다.

풀이 과정

2+5 -> 7
4+6 -> 0 // 1 다음으로 넘김
3+4 -> 7 + 1(승수) = 8

이렇게 동작 하게 만들면 된다.

최종 코드

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        answer_lst = ListNode() #정답을 답은 링크드 리스트
        curr_answer = answer_lst 
        
        curr_l1 = l1 
        curr_l2 = l2
        
        while True:
        	# 첫번째 리스트도 비고 두번째 리스트도 비었으면 더이상 할 게 없으므로 그만
            if not curr_l1 and not curr_l2:
                break
            
            # 이 전 노드에서 합이 10이 넘어가면 뒤로 1을 넘겨주는데
            # 그 넘겨받은 1이 있으면 고려해주기 위해
            _sum = curr_answer.val
            
            # 첫번 째 리스트가 비지않았으면
            if curr_l1:
            	# 값을 더해줌
                _sum += curr_l1.val
                
                # 다음 노드 가리키게
                curr_l1 = curr_l1.next
            
            # 두번 째 리스트가 비지않았으면
            if curr_l2:
            	# 값을 더해줌
                _sum += curr_l2.val
                # 다음 노드 가리키게 
                curr_l2 = curr_l2.next
            
            
            # 더한 값을 10으로 나눈 나머지 == 현재 정답 노드의 값이 됨
            remainder = _sum % 10
            
            # 더한 값을 10으로 나눈 몫 (승수, 뒤로 넘겨줄 수)
            share = _sum // 10
            
            # 현재 정답 노드의 값을 
            curr_answer.val = remainder
            
            # 이 조건을 걸지 않으면 7->0->8->0 이렇게 뒤에 쓸 데 없이 0이 생김
            # 어떤 리스트에도 다음으로 탐색해야할 노드가 없으면 추가할 필요가 없음
            # 즉 위의 예에서 두 리스트에 3번 째 노드들(3,4)을 더할 때는 다음 노드가 없으니까
            # 정답 노드에 뒤에 노드를 더 추가할 필요가 없음
            # 단, 이런 경우라도 승수가 있을 경우에는 넘겨줘야 하기 때문에 share 조건 추가
            if share or curr_l1 or curr_l2:
                curr_answer.next = ListNode(share)  
                curr_answer = curr_answer.next
       
        print(answer_lst)
        
        return answer_lst

이렇게 해서 통과했다.

주석 없는 코드

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        answer_lst = ListNode()
        curr_answer = answer_lst
        
        curr_l1 = l1
        curr_l2 = l2
  
        while True:
            if not curr_l1 and not curr_l2:
                break
            
            _sum = curr_answer.val

            if curr_l1:
                _sum += curr_l1.val
                curr_l1 = curr_l1.next
            
            if curr_l2:
                _sum += curr_l2.val
                curr_l2 = curr_l2.next
            
            remainder = _sum % 10
            share = _sum // 10
            
            curr_answer.val = remainder
            
            if share or curr_l1 or curr_l2:
                curr_answer.next = ListNode(share)  
                curr_answer = curr_answer.next

        return answer_lst

다른 사람의 풀이

def addTwoNumbers(self, l1, l2):
    dummy = cur = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        if l1:
            carry += l1.val
            l1 = l1.next
        if l2:
            carry += l2.val
            l2 = l2.next
        cur.next = ListNode(carry%10)
        cur = cur.next
        carry //= 10
    return dummy.next

로직은 거의 똑같은데 몇가지만 다르다.
첫번 째는 나는 l1,l2를 탐색할 때 새로운 변수로 탐색을 했는데 여기서는 l1,l2를 그대로 썼다.
진짜 생각해보니 굳이 새로운 변수를 만들어서 탐색할 필요가 없었다.

그리고 두번 째는 승수를 넘겨줄 때 하나의 변수를 계속 재활용했다는 점이다.
나는 현재 정답 노드의 다음 노드에다가 직접 할당을 해줬는데
이렇게 그냥 변수를 이용해서 하는 게 더 깔끔해보인다.