Week 1-2. [Linked List] 2. Add Two Numbers (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

https://leetcode.com/problems/add-two-numbers/?envType=study-plan-v2&envId=top-interview-150 

Add Two Numbers - LeetCode

두 개의 링크드 리스트가 주어진다. 주어진 링크드 리스트의 합을 계산하여 또 다른 링크드 리스트로 반환하라.

• 링크드 리스트에 숫자는 역순으로 저장된다. ex. 2->4->3 : 342
• 각 연결리스트의 head 노드는 0이 아니다.
• 각 연결리스트의 노드 수는 [1, 100]이다.
• Node.val은 [0, 9]이다.

 

🔎 어떤 식으로 접근했는가?

링크드 리스트에 숫자가 역순으로 저장된다. (head에서 tail 방향으로만 연결되어 있으므로 역순으로 탐색할 수는 없다.)

따라서 head부터 차례로 숫자를 만들어간 뒤 마지막에 reverse 해주어 합을 계산했다.

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

주어진 링크드 리스트의 원소를 하나씩 순회해야 하므로 linear search를 사용한다.

 

📝 의사 코드

head = l1
while head가 None이 아닌 동안:
	head.val을 L1에 누적한다
    head에 head.next를 대입한다
    
head = l2
while head가 None이 아닌 동안:
	head.val을 L2에 누적한다
    head에 head.next를 대입한다
    
int(L1[::-1])과 int(L2[::-1])를 합한다.

 

🎯 구현 코드

두 개의 링크드 리스트의 합을 계산하는 것까지 구현하였으나 또 다른 링크드 리스트를 만드는 방법을 잘 모르겠다.

# 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]:
       
        L1, L2 = '', '' # 각 연결리스트에 담긴 수를 저장할 문자열 (역순으로 합하기 위해 문자열에 저장한다)

        head = l1
        while head != None:
            L1 += str(head.val)
            head = head.next # 한 칸 이동

        head = l2
        while head != None:
            L2 += str(head.val)
            head = head.next # 한 칸 이동

		# 링크드 리스트에 숫자가 역순으로 저장되어 있었으니, reverse 하여 합한다.
        ans = int(L1[::-1]) + int(L2[::-1])

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

l1과 l2의 길이를 N이라고 할 때, 시간 복잡도는 O(N)이다.

 

✍️ 성능 회고

N이 최대 100이므로 O(N)으로 거뜬하다.

 

💡 무엇을/어떻게 개선할 수 있을까?

각 링크드 리스트를 순회하며 숫자를 만들 때, 문자열과 숫자의 변환이 잦아 헷갈린다.

처음부터 숫자로 만들 수는 없을까.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

L1과 L2의 타입을 문자열이 아닌 정수로 지정했다. 

연결리스트는 head와 linked_lst를 선언한 뒤 cur 노드를 생성하여 하나씩 이어붙인다.

# 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]:
       
        L1, L2 = 0, 0

        tmp = 1
        head = l1
        while head != None:
            L1 += head.val * tmp
            head = head.next # 노드 한 칸 이동
            tmp *= 10 # ✅ 자리 수 이동

        tmp = 1
        head = l2
        while head != None:
            L2 += head.val * tmp
            head = head.next # 노드 한 칸 이동
            tmp *= 10 # ✅ 자리 수 이동

        ans = L1 + L2

		# ✅ 새로운 연결리스트 생성
        head = None
        linked_lst = None
        for x in str(ans):
            if not head:
                head = ListNode(int(x))
                linked_lst = head
            else:
                cur = ListNode(int(x), linked_lst) # ✅ cur 노드의 next에 기존 노드(linked_lst)를 연결한다
                linked_lst = cur # ✅ 갱신
        return linked_lst

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

마찬가지로 O(N)의 시간복잡도를 갖는다.

 

느낀 점

링크드 리스트를 탐색하는 것은 익숙했으나 새로운 링크드 리스트를 생성하는 부분이 낯설었다.

하지만 구현은 생각보다 단순했다. 적응할 수 있도록 해야겠다.