#2 Add Two Numbers

전우재·2023년 8월 28일

leetcode

목록 보기

13/21

문제링크 - https://leetcode.com/problems/add-two-numbers/?envType=study-plan-v2&envId=top-interview-150

문제 조건

각 연결리스트의 노드 수의 범위는 다음과 같다 [1, 100].
0 <= Node.val <= 9
목록에는 앞에 0이 없는 것이 보장된다.
양수를 나타내는 LinkedList 2개를 받는다. 수는 역순으로 정렬되어 있다. 두 LinkedList가 나타내는 값을 더한 값을 배열에 역순으로 반환한다.

문제 해결

문제 해결 로직

해당 문제는 링크드리스트의 값을 가져와 계산된 결과를 배열에 나누어 저장하면 해당 문제를 해결할 수 있다.

**실패한 case**
1. 각 리스트들이 표현하는 값을 구한다.
2. 두 값의 합을 리스트 노드로 변환
해당하는 방법은 간단한 알고리즘으로 이해하기 쉬웠지만 다음과 같은 문제점을 겪었다.
- 너무 큰 수의 연산이라면 원하는 값이 나오지 않는다.
  - long으로 해결해보려고도 했지만 더 큰 수가 나오면 해결할 수 없었다.

그래서 각 자리마다 연산을 하여 너무 큰 합을 저장하지 않도록 했다.

현재 두 노드의 값을 구한다.
두 값의 합을 구한다(carry도 더한다.). 10으로 나눈 몫을 carry에 올림을 표시하고, 나머지는 결과의 현재 노드 값으로 저장한다.
결과의 현재 노드를 이동한다.
해당 과정을 l1와 l2 모두가 null이 될 때까지 반복한다.
마지막에도 carry가 남아있으면 해당 값을 노드에 추가하여 저장한다.
결과 연결리스트를 반환한다.

데이터 입력

문제에서 입력이 들어오는 데이터는 String s 하나지만 위치 관리를 위해 필요한 변수를 미리 선언해야합니다.

head
결과 노드리스트를 가리키는 head node
current
결과 노드리스트를 저장하기 위해 현재 node의 리스트를 가리키는 node
carry
올림 값을 표현하기 위한 변수
sum
현재 자리에 위치한 값의 합

  ListNode head = new ListNode(-1);
  ListNode current = head;
  int carry = 0;

각 자릿 수 합 구하기

각 노드의 현재 위치가 끝부분인지 확인한다.
이후 각 자리의 합을 구한다. 합에는 앞의 연산에서 발생한 올림을 더해준다.
합의 결과를 한자리수만 node에 추가한다.

         while (l1 != null || l2 != null) {
            int sum = carry;

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }

남은 결과 처리

두 node의 맨 끝에 도달했을 때, 올림이 남아있을 수 있다.
해당 결과도 결과 node에 마지막으로 추가해준다.

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

코드 작성

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int sum = carry;

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return dummy.next;
    }
}