[LeetCode] Add Two Numbers (못풀었다)

문제 출처 : 릿코드 (https://leetcode.com/problems/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.

 

두 개의 음이 아닌 정수를 나타내는 두 개의 비어 있지 않은 연결 목록 이 제공 됩니다. 숫자는 역순 으로 저장되며 각 노드에는 단일 숫자가 포함됩니다. 두 숫자를 더하고 합을 연결 목록으로 반환합니다.

숫자 0 자체를 제외하고 두 숫자에 선행 0이 포함되어 있지 않다고 가정할 수 있습니다.

 

예제

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

Explanation: 342 + 465 = 807.

 

접근 방식

ListNode라는 returnType을 보고 LinkedList가 생각이 났다. (처음엔 문제 상단에 Definition을 보지 못해서 혼자 한참 고민)

단방향 LinkedList 일까(?) 나름 생각하고 문제를 풀이를 시작했다.

1. 각 리스트들의 사이즈가 다를 것이니 null 체크를 꼭 해야 한다.

2. 각 노드의 값을 더해서 10을 넘으면 다음 노드 값의 합에 1을 추가해야겠다.

     1) 자릿수가 넘어가는지 확인하기 위해 변수를 하나 써야겠다 (carry)

     2) 두 리스트의 합을 담은 변수는 다음 반복문에서 carry 값 과는 다르게 초기화를 해줘야 한다.

3. 마지막 노드 두 개의 합이 10을 넘으면 리스트 마지막에 1을 추가해야겠다.

 

나의 풀이 (실패)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode resultNode = new ListNode();
        ListNode tmpNode = resultNode;
        int sumResult = 0;
        int carry = 0;

        while(l1 != null || l2 != null) {
            if(l1 != null) {
                sumResult += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                sumResult += l2.val;
                l2 = l2.next;
            }

            if(sumResult > 9) {
                sumResult -= 10;
                if(carry == 1) {
                    tmpNode = new ListNode(sumResult + carry);
                } else {
                    tmpNode = new ListNode(sumResult);
                }
                carry = 1;
            }else {
                if(carry == 1) {
                    tmpNode = new ListNode(sumResult + carry);
                } else {
                    tmpNode = new ListNode(sumResult);
                }
                carry = 0;
            }
            sumResult = 0;

            tmpNode.next = tmpNode;
        }
        if(carry == 1) {
            tmpNode.next = new ListNode(1);
        }

        return resultNode.next;
    }
}

어.. 이렇게 풀면 첫 번째 노드들의 합이 10이 넘을 경우에는 carry 값이 누락되는데...  개미지옥에 빠져버렸다..

이래서 코딩부터 하지 않고 논리를 세우고 코딩을 해야 하는데 손부터 나가는 습관이 다시 도졌다 ㅠㅠ

시간이 너무 늦어서 그런지 머리가 안 돌아간다 (라는 핑계)

한 시간 정도를 씨름하다가 결국 풀이를 찾기 시작했다

다른 블로거 분의 풀이를 보고 다시 풀어본다 (정답)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode resultNode = new ListNode();
        ListNode tmpNode = resultNode;
        int sumResult = 0;
        
        while(l1 != null || l2 != null) {
            sumResult = sumResult / 10;
        	if(l1 != null) {
        		sumResult += l1.val;
        		l1 = l1.next;
        	}
        	if(l2 != null) {
        		sumResult += l2.val;
        		l2 = l2.next;
        	}
        	
            tmpNode.next = new ListNode(sumResult % 10);
            tmpNode = tmpNode.next;
        }
        
        if(sumResult / 10 == 1){
            tmpNode.next = new ListNode(1);
        }
        
        return resultNode.next;
    }
}

풀이 출처 : https://madplay.github.io/post/leetcode-2-add-two-numbers

기가 막힌다.. 답을 보니까 단순하다고 생각이 드는데..

내일 다시 생각해봐야겠다!