[LEETCODE] 2: Add Two Numbers(Python)

Add Two Numbers - LeetCode

문제 설명

두 개의 단방향 연결 리스트가 주어질 때, 뒤에서부터 센 숫자(1→2→3이라면 숫자는 321)끼리 더한다. 더해서 나온 숫자를 역순 연결 리스트로 만들어 반환하는 문제이다.

나의 풀이

우선 단순히 더하는 것이 아니라 새로운 연결 리스트를 만들어야 한다.

1. 두 연결 리스트를 순회하며 값을 스택에 담는다.
2. 스택의 길이가 다르다면 짧은 쪽에 차이만큼 0을 채워준다. 이후 계산을 위해 두 스택 둘 다 0을 덧붙인다.
3. 두 스택의 자릿수별 합을 더해 새로운 덱을 만든다.
   • 덱의 현재 원소는 (l1[i]+l2[i])%10으로 설정한다.
   • 자릿수 올림을 위해 l1의 다음 원소에는 (l1[i]+l2[i])//10 값을 더해준다.
4. 합 덱의 맨 뒤 원소가 0이라면 제거한다.
5. 해당 덱에서 pop을 하며 새로운 연결 리스트를 생성한다.
6. 새롭게 만든 연결 리스트를 반환한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from collections import deque
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        s1=[]
        s2=[]
        while l1!=None:
            s1.append(l1.val)
            l1=l1.next
        while l2!=None:
            s2.append(l2.val)
            l2=l2.next
        
        n1=len(s1)
        n2=len(s2)
        if n1>n2:
            s2+=[0]*(n1-n2+1)
            s1+=[0]
        else:
            s1+=[0]*(n2-n1+1)
            s2+=[0]
        
        s=deque([0]*len(s1))
        for i in range(len(s1)-1):
            s[i]+=(s1[i]+s2[i])%10
            s1[i+1]+=(s1[i]+s2[i])//10
        s[-1]+=s1[-1]
        if s[-1]==0:
            s.pop()
        
        x=s.popleft()
        answer=ListNode(x,None)
        head=answer
        for i in range(len(s)):
            x=s.popleft()
            answer.next=ListNode(x,None)
            answer=answer.next
        return head

시간복잡도

두 연결 리스트 순회에 O(2*n), 자릿수별 합을 구하는 데에 O(n), 새 연결 리스트를 만드는 데에 O(n)이 걸려 전체 시간복잡도도 O(n)이다.