LeetCode2: Add Two Numbers - LinkedList/연결리스트 두개 숫자 더하기

문제 해석:

두개의 연결리스트가 주어지는데 이는 비어있지 않고, 음수가 아닌 integer이다. 숫자가 역순으로 저장되어있으며 각각의 노드는 각각의 자리 수를 포함하고 있다. 두 수를 더하고 더한 값을 연결 리스트로 리턴해라.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

 

 

 

 

 

 

 

 

풀이:

친절하게도 한자리 수씩 담고 있고, 더한 리턴값 또한 역순으로 저장하면 되기때문에 자리수 끼리 더하면 되는 문제.

생각해야 할 점: 

• 리턴할때 첫번째 노드를 리턴해야하는것

자릿수들을 더하며 저장하다보면 점점 앞으로 올라가게 되는데 리턴할때 첫번째 노드를 리턴하는것은 생각도 못했다.

• 각 자리수를 더한 값이 10이 넘어갈때 그 다음 자리수에서 +1을 해야하는 것

첫번째 노드들의 합은 carry 0, sum 7 이 나오니 패스하고,

그 다음 4와 6의 합은 10이 나온다. 그렇다면 해당 노드에는 0을 저장하고, 다음자리수에 1을 더해야한다.

다음 3과 4의 합은 7이지만 앞에서 넘어간 1을 더해줘야하기때문에 8이된다. 

 

이것을 수식으로 바꿔주면,

sum 은 l1 + l2 + carry 이다.

sum 이 10이 넘어가면 carry에 1을 넘겨줘야하고, 해당 자리수에는 십의자리수를 제외한 일의 자리수만 남겨줘야한다.

예를들어 sum이 6 + 7로 13이 나왔으면 해당자리수에는 3만 남기고(sum % 10),  carry 는 1을 (sum / 10)가져가야한다.

 sum이 6 + 4로 10이 나왔으면 해당자리수에는 0만 남기고(sum % 10),  carry 는 1을 (sum / 10)가져가야한다.

그리고 그 carry 는 다음 턴(반복문의 다음 턴)으로 넘겨서 더해준다.

이해가 안되시면 여길 참고하며 한번 종이에 계산식을 직접 써보세요.

 

자세한건 아래의 슈도 코드로 함께 합시다.

슈도코드:

포인터를 새로 만든 의미는 위에서 언급했듯, 리턴값을 cur로 넘겨주면 그 cur는 마지막 노드이기 때문에 다음 노드가 가르키는 것이 없다.

그래서 7->0->8 순서로 노드에 넣어주고 다시 7을 가르키는 노드를 리턴해야한다. 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy << Listnode 하나를 만든다.
        ListNode cur = dummy << 현재 노드를 따라갈 포인터를 새로 만든다.
        int carry = 0 << 앞자리수로 넘길 캐리 변수
        while (l1 혹은 l2 가 null이 아니거나 carry가 1일때 ){
            int sum = 0
            if (l1 이 null이 아니면){
                sum에 l1값을 더해주고
                l1을 다음으로 넘긴다.
            }
            if (l2 이 null이 아니면){
                sum에 l2값을 더해주고
                l2을 다음으로 넘긴다.
            }
            sum 에 캐리를 더한 후
            캐리를 10으로 나눈다.
            현재 노드 cur의 다음노드에 sum % 10을 넣어준다.
            현재 노드를 다음 노드로 옮긴다.
        }
        리턴 dummy.next;
    }
}

코드:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;
        while ((l1 != null) || (l2 != null) || (carry == 1)){
            int sum = 0;
            if (l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }
            sum += carry;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }
        return dummy.next;
    }
}

---

어려운 문제 아닌데 접근을 잘못하면 한없이 어렵게 풀수도 있다.

본인 얘기 맞음...ㅠ