[2번] Add Two Numbers

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

우선 리스트 길이가 서로 다를 수 있으니 l1, l2중 더 긴 리스트의 크기를 최대로 잡아두고 시작한다.

이때 carry를 이용하여 합이 10이상이면 다음 자리수로 올림해준다.

마지막으로 for문 탈출 후 아직도 carry가 있으면 1을 추가해주고 return

소스 코드 : 

 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def getSize(self, cList):
        ret = 0
        while cList != None:
            ret += 1
            cList = cList.next
            
        return ret
        
    def addValue(self, ret, i, cList):
        if cList != None:
            ret[i] += cList.val
            return cList.next
        return cList
    
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
 
        len1 = self.getSize(l1)
        len2 = self.getSize(l2)
        
        ret = [0]*max(len1,len2)
        carry = False             
        
        for i in range(0, len(ret)):
            if carry:
                ret[i] += 1
                carry = False
            
            l1 = self.addValue(ret, i, l1)
            l2 = self.addValue(ret, i, l2)
            
            if ret[i] >= 10:
                ret[i] -= 10
                carry = True
            
        if carry:
            ret.append(1)
        
        return ret