[LeetCode] 2.add two number

리트코드 코딩 테스트 준비
https://leetcode.com/problems/add-two-numbers/
문제에 대한 자세한 설명은 다음 사이트에서 확인 할 수 있다.

❓ 문제

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

예를 들어 2->4->3 , 5->6->4 의 연결리스트가 있을때
243 + 564 = 807이 되고 이를 뒤짚은 후 연결리스트를 이용하여 7->0->8 로 표시해주는 문제이다.

❗ 접근 방법

LinkedList를 활용하는 문제라고 생각한다. 이미 문제에서 기본적인 클래스는 주어져있어서
str()함수와 list() 그리고 [::-1] reverse를
잘 활용하면 될 것 같았다.

링크드 리스트의 구조는 다음과 같이 작성하였다.
처음에 값이 없고 연결만 해주는 헤더 노드를 하나 생성한다.
그리고 커서 값을 헤더에다가 지정하고
header.next = newNode() 로 연결할 새로운 노드를 만든다.
만들고 나서는 커서값을 다음 노드로 curr = header.next를 이용하여 옮기고
노드가 만들어지면 뒤집은 숫자의 처음 값을 node.val에 삽입한다.
이것을 뒤집은 숫자 리스트의 마지막 값까지 반복하여 준다.
연결리스트의 마지막 next에는 아무 값도 삽입하지 않는다.

그리고 return header.next
를 이용하여 여태까지의 리스트

⭕ 내가 작성한 코드

# 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]:
        answer = ListNode()
        num1 = num2 = ""
        
        while l1:
            num1 += str(l1.val)
            l1 = l1.next
        while l2:
            num2 += str(l2.val)
            l2 = l2.next
        
        sum = str(int(num1[::-1]) + int(num2[::-1]))
    
        sum = sum[::-1]
        curr = answer
        
        for i in range(len(sum)) :
            curr.next = ListNode()
            curr = curr.next
            curr.val = sum[i]
       
        return answer.next

💯 다른사람이 풀이한 코드

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        def iterate(ll):
            listt = []
            current = ll
            while current != None:
                listt.append(current.val)
                current = current.next
            return listt
        
        list1, list2 = iterate(l1), iterate(l2)
        
        def convert(l):
            s = ''
            for i in l:
                s += str(i)
            integer = int(s[::-1])
            return integer
        
        int1, int2 = convert(list1), convert(list2)
        ans = str(int1+int2)[::-1]
        
        ansl = [int(c) for c in ans ]
        
        cur = dummy = ListNode(0)
        for i in ansl:
            cur.next = ListNode(i)
            cur = cur.next
        return dummy.next 

🧑🏻 후기

다른 사람의 풀이 방법으로 하면 57% 더 빨라지긴 하는데
reverse를 최소화 해서 그런거 같다.

링크드리스트의 개념을 다시 복습 할 수 있는 문제인거같다.