LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

digit를 숫자로 바꾸어서?

문제에 보면 digits가 reversed order로 되어 있다는 부분이 있다. 이 부분을 읽고 떠오르는 가장 1차원적인 풀이 방법은 아래와 같다.

1. l1와 l2를 뒤집는다.
2. l1과 l2를 순회하면서 각각의 숫자를 string으로 연결해준다
3. 구한 string을 Int로 바꾸어 준다.
4. 다 Int 값을 더한다
5. 다시 string으로 바꾸어서 digit를 뒤집는다
6. 해당 자리수를 링크드리스트로 바꾼다.

굉장히 코드가 길고 복잡할 것 같다. 이 풀이 방법으로 문제를 풀려면 왜 괜히 digits를 거꾸로 주나 이런 생각이 들 수 있다. 하지만 링크드리스트를 숫자로 바꾸는 과정을 거치지 않고 바로 문제를 풀면 오히려 digits를 그대로 주는 것은 배려가 된다.

1의 자리부터 더해서 바로 링크드리스트 만들기 (feat: 전가산기)

초등학교 때 산수를 배울 때를 생각해보자. 2개의 여러자리 숫자를 더할 때는 1의 자리부터 비교해서 더한다. 만약에 1의 자리 수 2개를 더했을 때 10이 넘는다면 1을 10의 자리 수를 더할 때 더해준다.

따라서 어차피 2개의 수를 더하려면 1의 자리수부터 더해야한다. 이런 경우 digit가 거꾸로된 링크드리스트의 경우 처음부터 더해가면서 새로운 링크드리스트를 만들면 된다.

답을 리턴할 때에도 digit를 거꾸로 리턴하면 되므로 이렇게 구한 링크드리스트를 그냥 리턴하면 된다. 문제가 매우 쉬워진다.

참고로 두개의 한자리 수를 입력 받아 현재 자리수와 올림 수를 리턴하는 논리회로를 전가산기 (Full Adder)라고 부른다. 컴퓨터의 핵심 논리회로 중에 하나로 대상이 이진수라는 것을 제외하면 아래 코드로 구현된 논리와 정확히 일치한다.

구체적인 구현은 코드에 주석으로 첨부한다.

코드

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var node1 = l1
        var node2 = l2
        
        // 나중에 답을 리턴하기 위한 가상의 node (head 앞에 있는 node)
        let beforeHead: ListNode? = ListNode(0)
        // 새 list의 현재 node
        var node = beforeHead
        
        // 합이 10이 넘으면 다음자리로 올리는 작업을 담당하는 변수
        var carry = 0
        
        while node1 != nil || node2 != nil || carry != 0 {
            // 현재 node의 val을 정하기 위해서 모든 값을 더한다.
            let sum = (node1?.val ?? 0) + (node2?.val ?? 0) + carry
            
            // sum을 10으로 나눈 몫과 나머지
            let (q, r) = sum.quotientAndRemainder(dividingBy: 10)
            carry = q // carry에 몫
            let next = ListNode(r) // 다음 node의 val에 나머지를 할당
            node?.next = next // 현재 node에 다음 node 연결
            
            // 현재 node 1칸 이동
            node = node?.next
            
            // l1, l2의 node 1칸 이동
            node1 = node1?.next
            node2 = node2?.next
        }
        
        // beforeHead는 무조건 현재 head를 next로 가지고 있으므로 force-unwrapping을 사용해도 안전함
            // 문제의 조건에서 l1과 l2는 non-empty라고 제시되어 있음.
        return beforeHead?.next!
    }
}

quotientAndRemainder

quotientAndRemainder는 Int에 정의된 메소드 중에 하나로 특정 수로 나누었을 때 몫과 나머지를 튜플의 형태로 리턴한다.

let result = 12.quotientAndRemainder(dividingBy: 10)
print(result.quotient)
print(result.remainder)

// 1
// 2