Leetcode 릿코드 3 - Add Two Numbers

오랜만에 릿코드 문제를 풀어보는 시간을 갖었다.

 

취업 중에는 거의 매일 하나 이상 문제를 풀어 보고 있었는데,

막상 취업이 되고 회사에서 하는 일을 따라가기 위해서 시간의 비중을 높이다 보니

취업 중에 하던 많은 것을 하지 못하게 되는 여러 가지 중 한 가지가 되어버렸다.

릿코드 3 - Add Two Numbers

그래서 오늘 문제를 풀어볼 퀴즈는

Add Two Numbers이다.

문제 설명이 다음과 같다.

 

두 개의 음이 아닌 정수를 나타내는 두 개의 비어 있지 않은 링크 리스트가 제공된다.
각 노드는 하나의 숫자 자릿수를 포함하며, 숫자는 역순으로 저장된다. 두 숫자를 더하고 링크드 리스트로 반환한다. 0을 제외한 두 숫자에는 선행 0이 포함되지 않는 것으로 가정할 수 있다.

예를 들자면

Example 1:
입력 (Input): l1 = [2,4,3], l2 = [5,6,4]
결과치 (Output): [7,0,8]
설명 (Explanation): 342 + 465 = 807.

Example 2:
입력 (Input): l1 = [0], l2 = [0]
결과치 (Output): [0]

Example 3:
입력 (Input): l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
결과치 (Output): [8,9,9,9,0,0,0,1]

나한테 익숙한 PHP언어를 통해 풀어 보겠다.

일단 리커젼 (Recurrsion)을 통한 방법이 쉬울 거 같다.

 

릿코드에서 PHP 언어 선택을 하면 밑과 같이 화면에 출력이 된다.

class Solution {
    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    function addTwoNumbers($l1, $l2) {
    }
}

addTwoNumbers()라는 함수가 불러지도록 그 이름은 유지하되

내가 원하는 데로 코딩을 하면 된다.

그래서 내가 생각한 방식은 밑과 같다.

class Solution {
    /**
     * @param ListNode $l1
     * @param ListNode $l2
     * @return ListNode
     */
    public function addTwoNumbers(?ListNode $node1, ?ListNode $node2, int $carry = 0): ?ListNode {
        if (!$node1 && !$node2) {
            if ($carry) {
                return new ListNode($carry, null);
            }

            return null;
        }

        $sum = $node1->val + $node2->val + $carry;

        $mod = $sum % 10;
        $carry = floor($sum / 10);

        return new ListNode($mod, $this->addTwoNumbers($node1->next, $node2->next, $carry));
    }
}