[Leetcode/Medium] 두 수의 덧셈 (2. Add Two Numbers, Swift)

https://leetcode.com/problems/add-two-numbers/

 

🤔 문제 설명

음이 아닌 정수를 나타내는 두 개의 연결 리스트가 제공된다.

각 연결 리스트는 역순으로 저장되어 있으며, 두 숫자를 더하고 합계를 연결 리스트로 반환하라.

l1 = [2,4,3], l2 = [5,6,4]
// [7,0,8] (342 + 465 = 807)

 

💡 풀이

첫 번째 생각했던 방식은 아래와 같다. *조금 복잡하니까 읽어보고 싶은 사람만 천천히 읽어볼 것

1. l1과 l2를 끝에까지 이동하면서 각각을 배열로 저장한 후, reversed로 뒤집고, 정수로 바꾼다. (ex. [2,4,3] -> [3,4,2] -> 342)
2. 두 정수 값을 더하고, 다시 배열로 저장한 후, reversed로 뒤집는다. (807 -> [8,0,7] -> [7,0,8])
3. 배열을 하나씩 반복하면서 연결 리스트로 차근차근 연결해 나간다.

하지만, 이 풀이가 딱 보이는 것과 같이 연결 리스트에서 Array로, Array에서 Int로 이어지는 비효율적인 풀이이기 때문에 Linked List의 특성 자체를 이용할 방법을 생각하게 되었다.
그리고 다시 문제를 봤을 때 그 자체로 연산이 가능하도록 두 번씩이나 뒤집는 이유를 알게 되었다고 한다...ㅎ..예시 문제를 기준으로 설명해 보겠다.

1. 첫 번째 l1과 l2 연결 리스트의 값 연산 (2 + 5 = 7)
2. 한 칸 이동, 두 번째 l1과 l2 연결 리스트의 값 연산 (4 + 6 = 10), 끝 자리만 넣어야 하기 때문에 % 연산자 필요! (10 % 10 = 0)
3. 한 칸 이동, 세 번째 l1과 l2 연결 리스트의 값 연산 (3 + 4 = 7) + 앞에서 넘어온 앞자리 (10 / 10 = 1) 추가

즉, 보면 알겠지만 연결 리스트의 값을 순차적으로 이동하면서 % 연산 값은 연결 리스트의 val 값으로 연결, / 연산 값은 다음 연산으로 연결의 반복인 것을 확인할 수 있었다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 20ms (Beats 57.46%), Memory : 15.23MB (Beats 93.34%)

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var result: ListNode = ListNode(0)  // 최종 결과 반환할 노드 (next부터)
        var current: ListNode? = result     // 이동하면서 노드 추가
        var list1: ListNode? = l1           // l1
        var list2: ListNode? = l2           // l2
        var next: Int = 0                   // 연산 값이 두자릿수일 떄 다음 값으로 넘길 값

        // 연산을 계속할 수 있을 때까지 반복 (l1이나 l2나 next값 중 하나라도 있는 경우)
        while (list1 != nil || list2 != nil || next != 0) {
            let sum = (list1?.val ?? 0) + (list2?.val ?? 0) + next
            next = sum/10
            current!.next = ListNode(sum%10)
            current = current!.next
            
            // 다음 l1, l2 이동
            if (list1 != nil) { list1 = list1!.next }
            if (list2 != nil) { list2 = list2!.next }
        }

        return result.next
    }
}