리트코드 2. Add Two Numbers JAVA

문제

문제 해석

문제 자체는 단순하다.
각각의 같은 순서에 해당하는 val을 더해라
대신 10의 자리 발생하면 다음 수로 올림을 해줘라 라는 코드다.

수도 코드

수도 코드
자릿수를 나타낼 up
반복문 탈출을 위한 flag 변수

while(flag)
    cl1 = l1
    cl2 = l2    첫 값은 비어 있지 않기 때문

    임시 변수에 값 할당
    if val2 = cl2가 null 이면 0 아니면 val
    val1 = cl1.val

    두개의 덧셈 의 나머지 저장할 변수
    up에 val2 + val2 /10 삽입

    증가 로직 구현
    if cl2만 다음이 없을 경우
        cl1에 하나 만들어준뒤
        next
        next
    if 둘 다 null
           flag = false
    if cl1만 null 일 경우
        cl2.val = 0으로 변경
        cl1 만 next
    나머지
        next
        next

이 코드에서 확인할 것은 조건문 4종 세트만 확인해보면된다.
자세한 것은 코드로 확인하자

코드

/**
 * 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 cl1 = l1;
        ListNode cl2 = l2;
        int up = 0;
        boolean flag = true;
        while(flag){
            int val1 = cl1.val;
            int val2 = cl2 != null ? cl2.val : 0;
            int tmp = (cl1.val + cl2.val + up) % 10;
            up = (cl1.val + cl2.val + up) /10;

            cl1.val = tmp;

            //if cl1 ==null 이고 cl2는 null이 아닐  새로 만들어 주고 아닐 경우에는 cl1을 그대로 유지한다.
            if(cl1.next == null && cl2.next != null){
                cl1.next = new ListNode();
                cl1 = cl1.next;
                cl2 = cl2.next;
            }else if(cl1.next == null && cl2.next == null){
                flag = false;
            }
            else if(cl1.next != null && cl2.next == null){
                cl2.val = 0;
                cl1 = cl1.next;
            }else{
                cl1 = cl1.next;
                cl2 = cl2.next;
            }
        }
        if(up != 0)
            cl1.next = new ListNode(1);
        return l1;
    }
}

이 문제를 풀 때 처음 결정하는 것이 새로운 ListNode를 만들 것인가 아니면 만들지 않을 것인가를 고민하는 것이다.

나는 기존에 존재하는 ListNode를 반환해주기로 결정했다.

위의 코드에서 봐야할 코드는 if문 4종 세트다.

1. cl2만 존재 할 때
   • 이 때는 cl1.next를 하나 만들고 cl1, cl2 를 모두 next 해준다.
2. 둘 다 없을 때
   • 탈출을 위한 조건이다.
3. cl1만 존재하고 cl2는 존재하지 않을 때
   • 이 때는 cl1만 next 시키고, cl2의 val을 0으로 바꿔준다.
4. 그외
   두개 다 next로 바꿔준다.

이렇게 문제를 풀게 되면

2ms 가 나오게 된다.
이 때 시간 복잡도는 O(n)이 걸릴 것이라고 생각이든다.
이유는 노드의 갯수만큼로직을 수행하기 때문이다.

다른 빠른 방법들이 존재하는 것 같다.

내 로직의 문제점

1. 불필요하게 변경을 하는 부분이 너무 많다.

다른 사람의 문제 풀이

 */
class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        var sum = sumLists(l1, l2, 0);
        System.gc();
        return sum;
    }

    public ListNode sumLists(ListNode l1, ListNode l2, Integer more) {
        if (l1 == null && l2 == null && more == null) {
            return null;
        }

        if (more == null) {
            more = 0;
        }

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

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

        if (more > 9) {
            return new ListNode(more - 10, sumLists(l1, l2, 1));
        }

        return new ListNode(more, sumLists(l1, l2, null));
    }

}