[ Leetcode ] 2. Add two numbers

Lutica_·2024년 6월 20일

coding test leetcode

Solve-Leetcode

목록 보기

1/2

풀어보기 : https://leetcode.com/problems/add-two-numbers/

문제

두개의 숫자가 10의 단위 수로 나누어 보관한 연결리스트로 주어진다.
이때, 연결리스트는 숫자 순서가 역순으로 보관되어있다.

실질적인 문제

주어진 두 연결리스트의 합을 가진 연결리스트를 return하는 함수를 작성하라.
단, 10을 초과하는 경우 다음 노드에 그 캐리를 더해야 한다.

풀이방안

일단 두 노드를 포인터로 잡고, 계속 전진하면서 두 수를 더한다.

이때, 캐리발생시 전파해주는 매개변수로 전파를 해준다!
이후 한 리스트라도 None를 만나면 그 노드부터는 0으로 취급하거나 무시한다.
그리고 맨 마지막에 캐리가 남는다면, 그 캐리를 맨 끝에 삽입한다.

1차 풀이

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        nowl1 = l1
        nowl2 = l2
        rt = ListNode()
        rtn = rt
        plus = 0
        while nowl1 is not None and nowl2 is not None :
            sumval = nowl1.val + nowl2.val + plus
            if sumval > 9 :
                plus = 1
                sumval = sumval - 10
            else :
                plus = 0
            rtn.val = sumval

            nowl1 = nowl1.next
            nowl2 = nowl2.next
            if nowl1 is None or nowl2 is None :
                break
            rtn2 = ListNode(0)
            rtn.next = rtn2
            rtn = rtn2
        
        if nowl1 is not None or nowl2 is not None :
            not_lost = None
            if nowl1 is None :
                not_lost = nowl2
            else :
                not_lost = nowl1
            while not_lost is not None :
                sums = not_lost.val + plus
                if sums > 9 :
                    plus = 1
                    sums = sums - 10
                else :
                    plus = 0
                new_node = ListNode(sums)
                rtn.next = new_node
                rtn = new_node
                not_lost = not_lost.next
        if plus != 0 :
            rtn.next = ListNode(1)

        return rt

그런데 이 코드, 직관적이기는 하겠지만 깔끔하지는 않았다.
왜냐하면, 한번에 검사를 마칠 수 있는 코드를 두번에 걸쳐 루프를 돌리게 했기 때문에, 코드의 길이가 너무 길어지고 의미도 살짝 부정확하다.
solution을 보고 살짝 고쳐봤는데 그 결과는 아래와 같다.

refactoring한 풀이

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        nowl1 = l1
        nowl2 = l2
        rt = ListNode()
        rtn = rt
        plus = 0
        while nowl1 or nowl2 :
            sumval = (nowl1.val if nowl1 else 0 )+ (nowl2.val if nowl2 else 0) + plus
            plus = sumval // 10
            sumval = sumval % 10
            rtn.val = sumval

            if nowl1 :
                nowl1 = nowl1.next
            if nowl2 :
                nowl2 = nowl2.next
            if nowl1 is None and nowl2 is None :
                break
            rtn2 = ListNode(0)
            rtn.next = rtn2
            rtn = rtn2


        if plus != 0 :
            rtn.next = ListNode(1)

        return rt