리트코드 - 2. Add Two Numbers

리트코드 - 2. Add Two Numbers

출처 - https://leetcode.com/problems/add-two-numbers/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 두 개의 비어있지 않은 연결 리스트는 두 개의 음수가 아닌 정수를 나타냅니다. 각 노드는 한 자릿수를 포함하며, 숫자는 거꾸로 저장되어 있습니다. 두 숫자를 더한 후 그 결과를 연결 리스트 형태로 반환하세요.

두 숫자에는 0을 제외한 어떠한 숫자도 선두에 0이 오지 않습니다.

 

의사코드

더미헤드 생성 현재노드 = 더미헤드 올림 = 0; 반복문시작(l1이 null 이 아니거나 l2가 null이 아닌 경우)     x = 0     y = 0     만약 l1이 null이 아니면         x = l1 value 대입         l1 = l1.next     만약 l2가 null이 아니면         y = l2 value 대입         l2 = l2.next     sum = x + y + 올림     올림 = sum / 10     현재노드의 다음값을 sum % 10로 value 생성     현재노드를 다음 노드로 이동 반복문종료 만약 올림이 남아있으면     현재노드의 다음값을 1로 value 생성 더미헤드.next 리턴

 

풀이코드

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode currentNode = dummyHead;
        int carry = 0;

        while (l1 != null || l2 != null) {
            int x = 0;
            int y = 0;
             
            if (l1 != null) {
                x = l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                y = l2.val;
                l2 = l2.next;
            }
            int sum = x + y + carry;
            carry = sum / 10;
            currentNode.next = new ListNode(sum % 10);

            currentNode = currentNode.next;
        }

        if (carry == 1) {
             currentNode.next = new ListNode(1);
        }

        return dummyHead.next;
    }
}

 

코드설명

dummyHead를 만들어 임의값을 넣고, currentNode를 dummyHead로 만들어준다.

 

l1 와 l2가 null 이 아닌 경우동안 반복순환한다.

l1이 null이 아닌 경우라면 x에 value를 대입하고, l2가 null이 아닌 경우라면 y에 value를 대입하고 각각의 경우 다음 노드로 이동한다.

대입한 x와 y를 더하는데(sum), 만약 올림값(carry)이 있었다면 더해준다.

 

올림값은 sum이 10 이상인 경우 1이 되어야 하므로 sum / 10 을 해주어 다음 순환시 적용된다.(처음값 carry = 0)

현재노드인 currentNode는 실제로는 dummyHead부터 시작이므로, sum % 10을 계산하여 다음 노드에 넣어준다.

 

이렇게 반복하면, l1과 l2의 두 값이 모두 null이면서 합이 딱 10이 되는 경우가 발생할수 있다.

따라서 마지막에 carry가 1인 경우 다음 노드를 하나 더 추가해주어야 한다.

 

시간복잡도 - O(Max(n,m))  (n과 m은 각각 l1과 l2 노드 갯수 크기, 정확히는 최대 n+1 또는 m+1 만큼 순회한다.)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

노드를 처음 접해보다보니 복잡한 문제가 나오니 어떻게 사용해야 하는지 익숙하지 않았다.

그래서 항상 그렇듯 기존 값을 가지고 어떻게 하려고 하다보니 계속 꼬여버렸다.

 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode answerNode = l1;
        while (l1 != null) {
            if (l2 != null) {
                l1.val += l2.val;
            }

            if (l1.val >= 10) {
                if (l1.next != null) {
                    l1.val %= 10;
                    l1.next.val += 1; 
                } else {
                    l1.val %= 10;
                    ListNode newNode = new ListNode(1, null);
                    l1.next = newNode;
                }
            }
            if (l2 != null) {
                l2 = l2.next;
            }

            l1 = l1.next;
                
        }
        return answerNode;
    }
}

처음에는 answerNode를 만들어서 l1시작부분에 놓고 l1에 따라 순차적으로 진행하고자 했다.

위 코드는 l1을 직접적으로 바꾸는 문제가 있었고,

이에따라 l1==null && l2 != null 일때 l1 != null && l2 ==null 일 때 등 수많은 분기에 따라 계산을 각각 따로 해줘야 한다는 것이었다.

분기가 너무 나눠져서 가독성도 떨어지고 가장 큰 문제는 적는 나조차도 헷갈렸다.

 

그래서 저번에 배웠듯 아이디어가 별로면 버리고 새로 만드는 방식을 취했다.

사실 약속한 시간은 30분~1시간 이상 해결이 안되면 다른 아이디어를 생각해보는 것이었는데... 성격이 그런건지 좀 집요한 부분이 있어 3~4시간 붙들다보니 제 꾀에 제가 빠진다고 머리가 멈춰버리는 문제가 발생했다.😅

 

어쨌든 그래서 다르게 든 생각은 구현 코드와 같이

원티드 프리온보딩에서 linkedlist를 구현한 코드를 공부할 때 있던 dummyHead와 currentNode를 활용하기로 했다.

 

그리고 val를 직접 다루지 않고 변수를 따로 두고 구현해보기로 했고 결과적으로 성공했다.

 

다른코드

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        int carry = 0;

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

            int sum = digit1 + digit2 + carry;
            int digit = sum % 10;
            carry = sum / 10;

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

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

        ListNode result = dummyHead.next;
        dummyHead.next = null;
        return result;
    }
}

내 코드와 거의 비슷한데 삼항연산자를 써서 가독성이 좋다.

근데 실무에서는 삼항연산자가 안좋다는 피드백(우테코 프리코스때 배움)이 있는데...코테에는 써도 되는건지 모르겠다.

 

 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode head = new ListNode(0), p = head;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) { sum += l1.val; l1 = l1.next; } 
            if (l2 != null) { sum += l2.val; l2 = l2.next; }
            p.next = new ListNode(sum % 10);
            p = p.next;
            carry = sum / 10;
        }
        return head.next;
    }
}

이런 코드고 있었다.

이러면 내 코드에서 마지막 if문 처리를 따로 안해도 되네...이건 좋은 것 같다.

 

정리

노드를 조금 더 잘 다뤄야 할 것 같다.