LeetCode 2 Add Two Numbers

nayu1105·2023년 8월 28일

leetcode 알고리즘

LeetCode

목록 보기

14/28

LeetCode 2 Add Two Numbers 풀러가기

문제

두 개의 ListNode가 주어진다. ListNode는 이진수를 의미한다.

value는 각 자리의 이진수, next는 다음 노드(다음 자릿수의 이진수)이다.

두 개의 ListNode의 합을 ListNode 형태로 반환하는 함수를 작성해라.

문제 분석

각 ListNode의 자릿수들의 합을 temp 에 저장하고, temp%10 은 value에 저장, temp는 temp/10으로 갱신하면서 ListNode의 끝까지 더하는 알고리즘을 짰다.

ListNode answer에 모든 결과를 저장하고, 이를 리턴하려고 생각했다.

이진수 합을 계속해서 더하며 다음 노드에 저장해야 해기에 ListNode next = answer.next 라고 초기화 하고,

계산할 값이 있을 경우 next.next에 새롭게 노드를 할당하고, next = next.next 로 주소를 바꾸었다.

위 부분이 이 알고리즘을 짜며 가장 어려웠던 부분이다.

또한, l1 와 l2 의 최속 길이가 1이기 때문에 answer의 최소 길이도 1일 수 있었다.

그래서 초기화 시 answer의 next를 할당하면 answer의 최소 길이가 2가 되어 오류가 발생했다.

그래서 answer의 next를 할당하는 부분은 while 문에 넣었고, while 문 밖에는 l1과 l2의 합 % 10, 즉 val 값만 할당하였다.

첫번째 시도(소요시간 : 30분)

/**
 * 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 answer = new ListNode((l1.val + l2.val)%10);        
        int temp  = (l1.val + l2.val)/10;
        l1 = l1.next;
        l2 = l2.next;
             
        ListNode next = answer;

        while(l1 != null || l2 != null){
            next.next = new ListNode();
            next = next.next;

            if(l1==null){
                temp += l2.val;
                l2 = l2.next;
            }else if(l2==null){
                temp += l1.val;
                l1 = l1.next;
            }
            else{
                temp += l1.val + l2.val;
                l1 = l1.next;
                l2 = l2.next;
            }

            next.val = temp%10;
            temp /= 10;            
        }

        if(temp != 0){
            next.next = new ListNode();
            next.next.val = temp;
        }

        return answer;
    }
}

결과 : 성공

Runtime

Memory

문제를 푸는데 꽤 시간이 걸렸지만, 결과가 시간이나 메모리도 잘 나와서 다행이었다.

다른분의 코드

다른 분들은 코드를 어떻게 짜셨는지 찾던 찰나에, 나와 비슷하지만 시간이 감소한 버전의 코드를 찾았다.

이 분은 리턴은 temp.next를 하셨다.

나는 리턴 answer를 하기 위해 while문 밖에 최초로 한번 무조건 val값을 저장하는 코드를 짰다.

리턴 answer을 해야한다는 생각에 갇혀서 위의 방법을 생각했는데, 이분과 같이 조건을 모두 while에 넣고, 리턴을 answer.next했다면 코드가 훨씬 짧아지고, 알아보기도 편했을 것 같다.

코드

/**
 * 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 temp = new ListNode(0);
        ListNode head = temp;
        int carry = 0;
        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;
            }

            carry=sum/10;

            sum %=10;

            head.next = new ListNode(sum);

            head = head.next;

        }

    return temp.next;

    }
}

결과

-Runtime_

Memory

이 분의 코드가 내가 처음 작성한 코드보다 속도가 1ms 빨랐다.

메모리 효율은 내가 좋았다.

while문을 깔끔하게 잘 만드셔서 참고하면 좋을 코드 같았다.

두번째 시도 (개선 : 시간 감소)

위 분의 코드를 보고 나의 while 문을 고쳐보기로 했다.

기존 코드에서 최초 1번은 할당하는 부분을 없애고,

next라는 노드를 만들고, 그 head를 answer에 저장해서 최종 리턴은 answer.next를 하도록 작성했다.

/**
 * 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 next = new ListNode();
        ListNode answer = next;

        int temp = 0;

        while(l1 != null || l2 != null){     
            next.next = new ListNode();
            next = next.next;     

            if(l1==null){
                temp += l2.val;
                l2 = l2.next;
            }else if(l2==null){
                temp += l1.val;
                l1 = l1.next;
            }
            else{
                temp += l1.val + l2.val;
                l1 = l1.next;
                l2 = l2.next;
            }

            next.val = temp%10;
            temp /= 10;
           
        }

        if(temp != 0){
            next.next = new ListNode();
            next = next.next;
            next.val = temp;
        }

        return answer.next;
    }
}