[LeetCode-자바] N_2 Add Two Numbers

📜 문제

• 숫자가 거꾸로 저장된 ListNode l1, l2가 주어진다.
• ListNode는 비어있지 않고 data값은 0이상이다.
• l1과 l2를 더한 결과값을 거꾸로 저장한 ListNode를 출력하라.

제약 조건 중 The number of nodes in each linked list is in the range [1, 100] 조건을 유의해야 한다.
최대 100자릿수를 가질 수 있으므로 전체 숫자를 더할 수 없다.
-> Long 범위 (2의 64승) = 19자릿수

백문이불여일견이니 무슨 말인지는 코드로 설명하겠다..

---

✍ 부분 코드 설명

변수 선언

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode tmp = result;
        int carry =0;
        ...

result: 결과로 출력할 ListNode
l1, l2 : 피연산자
tmp: result의 맨 마지막 노드를 가리킬 임시 노드
carry: 올림수

---

덧셈 과정

		...
        
     while(l1!=null || l2!=null||carry!=0){
            int d1 = (l1!=null)?l1.val:0;
            int d2 = (l2!=null)?l2.val:0;

            int sum = d1+d2+carry;
            int digit = sum%10;
            carry = sum/10;

            ListNode newNode = new ListNode(digit);
            tmp.next = newNode;
            tmp = tmp.next;

            l1 = (l1!=null)?l1.next:null;
            l2 = (l2!=null)?l2.next:null;
        }
        return result.next;
    }

- 피연산자도 거꾸로 저장돼 있고, 결과값도 거꾸로 출력해야 하기 때문에 굳이 Reverse하지 않고 풀 수 있다.

개인적으로 문제 풀이의 핵심은 carry를 이용하는 것이라고 생각한다.

우리가 덧셈을 할 때 더한 값이 10을 초과하는 경우, 앞자리 수에 1을 올려주는 것을 코드로 작성했다.

Ex)
l1 : 2 -> 4 -> 3
l2: 5 -> 6 -> 4
result : 7 -> 0 -> 8

1) d1 = 2, d2 = 5
sum = 2+5+0 = 7
digit = 7
carry = 0
tmp: 7 -> null

2) d1= 4, d2 = 6
sum = 4+6+0 = 10
digit = 0
carry = 1
tmp: 7 -> 0 -> null

3) d1 = 3, d2 = 4
sum = 3+4+1 = 8
digit = 8
carry = 0
tmp = 7 -> 0 -> 8 -> null

result = 7 -> 0 -> 8

---

🍳 전체 소스 코드

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode tmp = result;
        int carry =0;
        while(l1!=null || l2!=null||carry!=0){
            int d1 = (l1!=null)?l1.val:0;
            int d2 = (l2!=null)?l2.val:0;

            int sum = d1+d2+carry;
            int digit = sum%10;
            carry = sum/10;

            ListNode newNode = new ListNode(digit);
            tmp.next = newNode;
            tmp = tmp.next;

            l1 = (l1!=null)?l1.next:null;
            l2 = (l2!=null)?l2.next:null;
        }
        return result.next;
    }
}

---

✨ 결과

약 2시간동안 헤매다 풀이를 보고 해결한 문제다.
2시간이나 고민한 게 무색할 정도로 정답 풀이는 단순하고 멋졌다.

내가 어떻게 접근했는지, 그리고 이게 왜 틀렸는지 설명하겠다.

---

🍰 시도한 풀이

- ListNode를 역순으로 재배치 하고, 더하기

접근 방식: 주어진 l1, l2가 역순이니까 다시 역순으로 재배치 하고, 이 둘을 더한 결과를 저장해서, 뒤에서부터 ListNode에 추가해 풀어보자!

1. 리스트 역순으로 재배치

 public static ListNode reverse(ListNode list){
        ListNode cur =null;
        ListNode nextNode = list;
        ListNode reverse = cur;
        while(nextNode!=null){
            cur = nextNode;
            nextNode = nextNode.next;
            cur.next = reverse;
            reverse = cur;
        }
        return reverse;
    }

2. 연결리스트의 노드를 문자열로 합치기

  public static String IntToStr(ListNode list){
       String str ="";
       while(list!=null){
           str+=String.valueOf(list.val);
           list = list.next;
       }
       return str;
   }

문자열로 변환한 이유는 노드에 저장된 값이 100의 자리인지 10의 자리인지 자릿수를 알 수 없기 때문에 문자열로 연결했다.

3. 노드 삽입

  public static ListNode insertNode(int val,ListNode result){
       ListNode newNode = new ListNode(val);

       if(result == null){
           return newNode;
       }
       else{
           ListNode tmp = result;
           while(tmp.next!=null){
               tmp = tmp.next;
           }
           tmp.next = newNode;
       }
       return result;
   }

4. Main

// 메인 코드
 public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = new ListNode();
        ListNode r2 = new ListNode();

        r1 = reverse(l1);
        r2 = reverse(l2);
        printList(r1);

        String s1 = IntToStr(r1);
        String s2 = IntToStr(r2);

        long res = Long.parseLong(s1)+Long.parseLong(s2);
        ListNode result = new ListNode();
        while(true){
            long addValue = res%10;
            result = insertNode((int)addValue,result);

            if(res/10 == 0) break;
            res /=10;
        }

        printList(result);
        //System.out.print(res);
        return result.next;
    }
    

실행 과정

• 먼저 r1, r2에 각각 l1과 l2를 역순으로 재배치한 값을 저장한다.
• 리스트의 모든 요소를 문자열로 변환하고, 다시 Long 형으로 변환한 값을 res 변수에 저장한다.
• 역순으로 결과를 출력해야 하므로 1의자리부터 저장한다.
• 결과값을 반환한다.

해당 코드로 TestCase는 통과 했지만,
문제는 result 변수에 약 20자릿수 이상이 들어오는 경우에 발생했다.

앞서 말했듯 제약조건에 명시된 것처럼 최대 자릿수가 100개가 들어올 수 있기 때문에 Long형으로 더한 값을 저장하려면 택도 없었다..

이제 제약조건도 잘 보고 좀 생각해서 풀어야겠다.
빨리 코드를 치고 싶어서 찔끔 생각하고 접근하니 요렇게 바보같이 풀었다.
최소 5분은 생각하고 풀자~~ 제발