Leetcode - Add Two Numbers

wanderer-s·2021년 11월 25일
0

Algorithm

목록 보기
1/19
post-thumbnail

Problem

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개의 링크드 리스트가 주어진다.
숫자는 역순으로 저장되어 있으며, 각 노드는 하나의 숫자를 포함한다.
두 숫자의 합을 링크드 리스트로 반환하라.

2개의 숫자는 숫자 자체가 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]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Solution

JavaScript

  1. 첫번째 시도
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  	// 역순으로 되어있는 linked list를 순차적으로 바꾸면서 하나의 숫자로 반환하는 함수
    function mergeToNum(linkedList) {
        let number = '' // 각 자리별로 숫자를 합치기 위해 문자열로 시작
        while(linkedList) {
            number = linkedList.val + number
            linkedList = linkedList.next
        }
        return +number // 결과는 숫자형으로 반환
    }
    
  	// 2개의 숫자를 더함
    const resultNumber = mergeToNum(l1) + mergeToNum(l2)
    console.log(BigInt(mergeToNum(l1)))
    console.log(BigInt(mergeToNum(l2)))
    
  	// 더한 숫자를 다시 문자열화
    const stringNumber = '' + resultNumber
    let node
    // 문자열화 한 숫자를 linked list로 만드는 과정
    for(let i = stringNumber.length - 1; i >= 0; i-- ) {
        if(!node) {
            node = new ListNode(stringNumber[i])
        } else {
            let temp = node
            while(temp.next) {
                temp = temp.next
            }
            temp.next = new ListNode(stringNumber[i])
        }
    }
    return node
};

첫번째 시도의 결과는 input으로 들어온 linked list가 길면 통과하지 못했다
숫자가 1e+3 와 같은 지수표기법 형태로 반환되었기때문
따라서 이를 처리하기 위해 BigInt 처리를 하였다

  1. 두번째 시도
    첫번째와 거의 흡사하지만 mergeToNum 함수의 반환값을 BigInt로 변경해주었다
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    function mergeToNum(linkedList) {
        let number = ''
        while(linkedList) {
            number = linkedList.val + number
            linkedList = linkedList.next
        }
        return BigInt(number)
    }
    
    const resultNumber = mergeToNum(l1) + mergeToNum(l2)
    const stringNumber = '' + resultNumber
    let node
    for(let i = stringNumber.length - 1; i >= 0; i-- ) {
        if(!node) {
            node = new ListNode(stringNumber[i])
        } else {
            let temp = node
            while(temp.next) {
                temp = temp.next
            }
            temp.next = new ListNode(stringNumber[i])
        }
    }
    return node
};

통과는 되었으나 효율적인 코드는 아닌것으로 판단된다. 추후에 다른 방식으로 접근하는지 더 시도해봐야겠다

Feedback은 언제나 환영입니다🤗

profile
You only get one life. It's actually your duty to live it as fully as possible.

0개의 댓글