LeetCode 2. Add Two Numbers

문제 요약: 2개의 Number형 자료구조(링크드리스트와 유사)가 주어졌을때, 각각의 원소를 더한 자료구조 (input과 같은)를 반환 하시오. 

만약, 길이가 다르면 남는 원소 그대로 반환. 단 두자리수가 넘어가면 다음 링크드 리스트의 원소의 값에 1을 더한다.

 

예:

input:

2 -> 4 -> 3

5 -> 6 -> 4

output:

7 -> 0 -> 8

 

input:

9 -> 9 -> 9 -> 9 -> 9 -> 9

9 -> 9 -> 9

output:

8 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1

 

input:

2 -> 4 -> 9

5 -> 6 -> 4 -> 9

output:

7 -> 0 -> 4 -> 0 -> 1

 

문제 접근: 처음에는 input 각각 반복문으로 루프 하나가 진행될때마다 10의 제곱을 해서 각각 더해서 다시 나누면서 결과를 만들면 된다고 생각하여 풀었었는데, java 기준 특정 케이스에서 integer overflow가 발생한다. 좀 더 생각해보니, 두개의 input을 한번에 루프를 돌면서 10넘어갈 경우 임시변수에다가 체크를 해준뒤 계속 이어나가면 쉽게 풀린다.

 

구현 코드: Java 사용

/**
 * 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) {
    	// input이 둘다 null이면 바로 종료.
    	if (l1 == null && l2 == null) return null;
        
        // input 두개 더했을때 10이 넘어가면 체크해줄 변수
        int carry = 0;
        // 반환할 변수
        ListNode result = null;
        // result next를 추적할 변수
        ListNode copy = null;
        
        // carry는 0또는 1만 넣을건데,
        // 1이면 이전 값이 10이넘어가는거기 때문에 ListNode(1)을 추가해 줘야함.
        while (l1 != null || l2 != null || carry > 0) {
        	int sum = 0;
            if (l1 != null) {
            	sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
            	sum += l2.val;
                l2 = l2.next;
            }
            // 이전에 10이 넘는 값이었다면 현재 sum값에 1을 더함.
            if (carry > 0) {
            	sum += 1;
            }
            
            // 두 input의 합이 10이 넘으면 10이 넘는다고 표시, 아니면 0으로 표시
            if (sum >= 10) {
            	sum -= 10;
                carry = 1;
            } else {
            	carry = 0;
            }
            
            // 처음일 경우와 2번째 루프일때 구분하기 위해 작성.
            if (result == null) {
            	result = new ListNode(sum);
                copy = result;
            } else {
            	copy.next = new ListNode(sum);
                copy = copy.next;
            }
        }
        return result;
    }
 }

문제를 이해하는게 가장 어려운거 같다..