[Leetcode] 2번 - 두 수의 합

1. 문제 파악

1. 문제 링크: https://leetcode.com/problems/two-sum/description/
2. 문제 정의: 주어진 두 연결리스트의 각 노드에 저장된 숫자를 더해서 새로운 연결리스트를 생성해라.
3. 문제 주의점:
   1. 주어진 두 연결리스트의 노드 개수가 다를 수 있다.
   2. 두 개의 노드의 수를 저장한 값이 올림수가 있을경우, 주어진 연결리스트보다 노드 개수가 많은 연결리스트가 생성될수있다.
4. 시간복잡도: O(N)

---

2. 문제 풀이

1. 핵심 문제 풀이 도출(문제 의도 파악)

일단, 두개의 연결리스트를 순차적으로 노드를 순회하면서 덧셈을 진행하면 된다. 이렇게 덧셈을 진행해서 반환을 위한 새로운 연결리스트가 완성될때까지 반복문을 수행한다. 하지만, 위의 문제 주의점에서 두개의 조건에 따라 반복문 탈출조건을 설정해야한다.

1. 주어진 두 연결리스트의 노드 개수가 다를수있음 -> 반복문에서 탈출조건이 두 연결리스트의 이동한 노드가 모두 null이면 탈출이 아니다.
2. 두 수의 합이 올림수가 있을 경우에 주어진 연결리스트보다 노드 개수가 많은 연결리스트가 생성될수있음 -> 긴 연결리스트가 null이 될때까지는 최소 반복해야한다.

따라서 연결리스트가 하나라도 null이 아니거나 올림수가 존재하면, 반환을 위한 연결리스트 생성 로직을 반복하도록한다.

1. 연결리스트가 하나라도 null이 아니거나 올림수가 존재하면 아래의 로직을 반복한다.
2. l1, l2 연결리스트를 순회하면서 두 개의 수와 올림수를 더한 합을 계산한다.
3. 합에서 10으로 나눈 수의 몫을 올림수에 저장한다.
4. 합에서 10으로 나눈 수의 나머지를 가진 노드를 생성한다.
5. 반환할 연결리스트에 노드를 연결한다.
6. l1, l2 연결리스트의 순회중인 노드가 null이 아니면 다음 노드로 이동한다.
7. 생성한 연결리스트를 반환한다.

 

2. 입출력 케이스 도출 및 문제 풀이 도출 확인

• 일반 케이스
  • EX1
    • Input: l1 = [2,4,3], l2 = [5,6,4]
    • Output: [7,0,8]
  • EX2
    • Input: l1 = [0], l2 = [0]
    • Output: [0]
• 엣지 케이스
  • Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  • Output: [8,9,9,9,0,0,0,1]

 

3. 코드 구현

/**
 * 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 dummy = new ListNode();
        ListNode cur = dummy;
        int carry = 0; // 올림수를 초기화해서 첫번째 연산때 0으로 사용
        // 연결리스트가 하나라도 null이 아니거나 올림수가 존재하면 반복한다.
        while (l1 != null || l2 != null || carry != 0) {
            int v1 = l1 != null ? l1.val : 0; // l1이 null이면 0으로 설정해서 덧셈 무효화
            int v2 = l2 != null ? l2.val : 0; // l2이 null이면 0으로 설정해서 덧셈 무효화
            int sum = v1 + v2 + carry; // l1, l2 연결리스트를 순회하면서 두개의 수와 올림수를 더한 합을 계산한다.
            carry = sum / 10; // 합에서 10으로 나눈 수의 몫을 올림수에 저장한다.  
            int digit = sum % 10; // 합에서 10으로 나눈 수의 나머지를 가진 노드를 생성한다.
            cur.next = new ListNode(digit); // 반환할 연결리스트에 노드를 연결한다.
            cur = cur.next; // 연결한 다음 노드로 이동

            // 이동할 노드가 null 이 아닐 경우에만 이동
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        } 
        return dummy.next; // 더미 노드의 다음 노드부터 반환할 연결리스트의 head
    }
}

 

4. 복잡도

• 시간 복잡도
  • 연결리스트 순회: O(N)
• 공간 복잡도
  • 추가 공간은 결과값을 저장할 연결리스트를 생성하기때문에 O(N)이다.