[파이썬/Python] Leet Code 2(Medium): Add Two Numbers

📌 문제 : Leet Code 2

---

📌 문제 탐색하기

ListNode : 연결 리스트의 노드 개수 ($1 ≤ ListNode ≤ 100$)
Node.val : 노드 안의 정수 ($0 ≤ Node.val ≤ 9$)

문제 풀이

2개의 연결 리스트 내에 음이 아닌 정수가 노드마다 1개씩 들어가 있는 상태이다.
연결 리스트 내의 노드를 역순으로 해서 정수로 만들고 그렇게 만들어진 2개의 정수를 더한 후 역순으로 새로운 연결 리스트 노드에 넣어주어 반환하는 문제이다.

이 문제는 리스트에 넣어 역순 정렬, 형변환, 덧셈을 진행해서 해결했다.

1. 2개의 연결 리스트를 순회하면서 노드의 정수를 리스트에 넣는다.
2. 역순 정렬한다.
3. 각 요소를 문자열로 형변환한다.
4. 리스트 요소들을 하나의 문자열로 변환한다
5. 2개의 문자열을 정수로 형변환하고 덧셈한다.
6. 덧셈 결과를 다시 문자열로 형변환해 리스트에 넣어준다.
7. 역순 정렬하고 각 요소를 정수형으로 바꾼다.
8. 이 리스트의 요소들을 새로 만든 연결 리스트에 하나씩 넣는다.

가능한 시간복잡도

연결리스트 노드의 정수를 리스트에 넣기 → $O(노드 개수) = O(n)$
순서 뒤집기 → $O(노드 개수) = O(n)$
문자열 변환 → $O(노드 개수) = O(n)$
리스트 요소 합치기 → $O(노드 개수) = O(n)$
형변환 후 리스트 넣기 → $O(노드 개수) = O(n)$
연결 리스트 만들어 넣기 → $O(노드 개수) = O(n)$

최종 시간복잡도
최악일 때 $O(n) = O(100)$이 되는데 이는 충분히 수행 가능하다.

알고리즘 선택

• 연결리스트의 노드들을 순회하면서 리스트에 넣고 연산 후 새 연결 리스트에 값 넣어주기

---

📌 코드 설계하기

1. 리스트 정의
2. 리스트에 넣기
3. 순서 뒤집기
4. 요소들 문자열 변환
5. 리스트 요소 합치기
6. 덧셈 연산 후 형변환해 리스트에 넣기
7. 역순으로 바꾸기
8. 요소들 정수형으로 변환
9. 연결리스트에 넣기

---

📌 시도 회차 수정 사항

1회차

• Memory Limit Exceeded
• 연결리스트 l1을 순환하면서 리스트에 하나씩 넣는 코드에서 다음 노드로 넘어가는 부분을 구현해주지 않아서 발생했다.

2회차

• 리스트의 요소들을 하나로 합치는 ''.join() 함수는 내부의 요소들이 문자열일때만 동작 가능하다.
• 각 요소를 문자열로 바꿔준 후 합쳤다.

3회차

• 만든 정답을 리스트로 반환에 발생한 문제였다.
• 리스트를 연결리스트로 만들어주는 과정이 필요했다.

---

📌 정답 코드

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 리스트 정의
        li_l1 = []
        li_l2 = []

        # 리스트에 넣기
        while True:
            li_l1.append(l1.val)
            if l1.next == None:
                break
            l1 = l1.next

        while True:
            li_l2.append(l2.val)
            if l2.next == None:
                break
            l2 = l2.next

        # 순서 뒤집기
        li_l1 = li_l1[::-1]
        li_l2 = li_l2[::-1]

        # 요소들 문자열로 변환
        for i in range(len(li_l1)):
            li_l1[i] = str(li_l1[i])

        for i in range(len(li_l2)):
            li_l2[i] = str(li_l2[i])
        

        # 리스트 요소 합치기
        li_l1 = ''.join(li_l1)
        li_l2 = ''.join(li_l2)

        # 덧셈 연산 후 형변환하고 리스트에 넣기
        li_answer = list(str(int(li_l1) + int(li_l2)))
        
        # 역순으로 바꾸기
        li_answer = li_answer[::-1]

        # 요소들 정수형으로 변환
        li_answer = [int(x) for x in li_answer]

        # 연결리스트에 넣기
        head = ListNode(li_answer[0])

        current = head
        for i in range(1, len(li_answer)):
            current.next = ListNode(li_answer[i])
            current = current.next

        return head

• 결과
  

---

👍 다른 풀이1

class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        dummyHead = ListNode(0)
        curr = dummyHead
        carry = 0
        
        while l1 != None or l2 != None or carry != 0:
            l1Val = l1.val if l1 else 0
            l2Val = l2.val if l2 else 0
            columnSum = l1Val + l2Val + carry
            carry = columnSum // 10
            newNode = ListNode(columnSum % 10)
            curr.next = newNode
            curr = newNode
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
            
        return dummyHead.next

• 진행
  • 연결 리스트 노드를 직접 순회하여 계산
  • 자리수끼리 더하고 자리 올림할 숫자를 carry에 저장하면서 활용
  • 한 자리 덧셈 결과를 바로 연결 리스트에 저장
• 장점
  • 자료구조 변환 X
  • 연결 리스트를 1번 순회
  • 새 연결 리스트만 만들어서 불필요한 중간 데이터 X

👍 다른 풀이2

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy
        remainder = 0
        
        while l1 or l2 or remainder:
            total = remainder

            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            remainder = total // 10
            curr.next = ListNode(total % 10)
            curr = curr.next

        return dummy.next

• Runtime이 0ms인 코드이다.
• 진행
  • 2개의 연결 리스트를 한 번에 순회하여 각 자리의 숫자 합을 계산
  • 올림 수는 remainder 변수에 저장해 다음 자릿수에 반영
  • 새 노드를 바로 생성해 결과 리스트를 연결
• 장점
  • 연결 리스트를 그대로 사용해 1번의 순회로 결과 생성
  • 리스트 변환, 문자열 변환, 역순 정렬 X
  • 메모리 할당, 데이터 복사 최소화

---

✏️ 회고

• 연결리스트 구현에 대한 이해도가 많이 떨어졌다는 것을 느꼈다.
• Leet Code의 맨 위에 정의된 부분을 이해하는데도 시간이 걸렸다. 그 정의가 연결 리스트 자체를 구현한 것인 줄 알고 코드를 작성했는데 연결 리스트의 노드라는 것을 나중에 깨달아서 많이 헤맸다.
• 다른 코드를 보면서 얼마나 비효율적으로 코드를 작성하고 있는지 알 수 있었다. 연결리스트라는 자료구조에 대해 정확히 알지 못해서 장점을 전혀 활용하지 못했다.
• 자료 구조 공부의 필요성을 제대로 느꼈다. 그리고 요즘엔 문제 해결만 하면 끝이라 생각해서 다른 코드들을 찾아볼 생각을 안했었는데 오늘부터는 다시 더 나은 코드들도 찾아보면서 공부해야 겠다고 다짐했다.