LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 양수로만 이루어진 값을 가지고 있는 연결 리스트 2개

2. output: 두 연결 리스트의 합을 나타내는 연결 리스트 리턴

   ex) 2 → 4 → 3, 5 → 6→ 4 ⇒ 7 → 0 → 8

   • 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.

Idea

문제의 풀이 자체는 크게 어려움 없이, 재귀나 탐색을 통해 각 노드의 값을 더하고, 10을 넘는 경우만 처리해주면 되었다.

여태 알고리즘을 풀며 연결리스트의 head 노드를 리턴하는 경우가 없었기 때문에 당연히 배열로 output을 리턴해야 한다고 생각했다.

하지만 계속해서 좋지 않은 점수가 나와서, 정답 코드를 확인하였고 head 노드를 리턴해도 된다는 것을 발견했다.

head 노드를 리턴하여 연결리스트를 output으로 전달하는 경우, 탐색, 덧셈, 리턴이 한번에 가능하기 때문에 높은 점수를 받을 수 있었다.

Solution

1. 재귀 함수로 연결리스트 탐색 ⭕

   연결리스트 탐색 후 문자열 리턴 → 배열

   각 배열을 한칸씩 더하기 → 배열 리턴

   /**
    * Example:
    * var li = ListNode(5)
    * var v = li.`val`
    * Definition for singly-linked list.
    * class ListNode(var `val`: Int) {
    *     var next: ListNode? = null
    * }
    */
   class Solution {
       var sum = 0
       fun addTwoNumbers(l1: ListNode?, l2: ListNode?): List<Int> {
           val num1 = search(l1)
           val num2 = search(l2)
   				// 마지막 수의 합이 10 이상인 경우를 위해 length + 1
           var result = Array<Int>(Math.max(num1.length, num2.length) + 1) {0}
           for (i in 0..result.size-2) {
               if (i < num1.length) result[i] += num1[i].toString().toInt()
               if (i < num2.length) result[i] += num2[i].toString().toInt()
               if (result[i] >= 10) { // 합이 10 이상인 경우 처리
                   result[i] = result[i] - 10
                   result[i+1] += 1
               }
   
           }
           if (result.last() == 0)
               return result.slice(0..result.size-2)
           return result.toList()
       }
   		
   		// 연결리스트 재귀 탐색하여 문자열 리턴
       fun search(node: ListNode?): String {
           if (node == null) return ""
           return node.`val`.toString() + search(node.next)
       }
   }
   

   시간 복잡도: 연결리스트 탐색 + 문자열 순회 = n

   

2. 연결리스트를 리턴 ⭕

   두 연결리스트를 탐색하며, 바로 값을 더한 연결리스트 리턴

   class Solution {
       fun addTwoNumbers(l1: ListNode?, l2: ListNode?, ten: Int = 0): ListNode? {
           // 두 연결리스트 모두 null 노드이면서 넘어오는 값(10) 없는 경우
           return if (l1 == null && l2 == null && ten == 0) null
           else {
               val s = (l1?.`val` ?: 0) + (l2?.`val` ?: 0) + ten // nums1, nums2 노드 값 + (이전 합의 10)
               ListNode(s % 10).apply { next = addTwoNumbers(l1?.next, l2?.next, s / 10) }
           }
       }
   }
   

   시간 복잡도: 연결리스트 순회 = n

   

Point

1. 사실 두 풀이의 시간 복잡도가 같아서 평가에 비해 큰 차이가 있진 않음