[Leetcode 2] Add Two Numbers - 전가산기,연결리스트

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

Problems

리스트 두개를 역순으로 만들고 연결리스트의 숫자를 더한다. 그다음 역순으로 리스트를 만들어서 반환해라

 

input = l1 : {2,4,3}  l2: {5,6,4}

output = {7,0,8}

 

설명 :

2->4->3 을 뒤집으면 3->4->2

5->6->4을 뒤집으면 4->6->5

342+465 = 807

807을 7->0->8인 연결리스트로 반환.

---

전략 1. 브루드포스

 

가장 떠올리기 쉬운 방법으로는 다음 순서로 진행하면 된다.

 

1. 2개의 연결리스트를 뒤집는다.

2. 2개의 연결리스트를 각각 정수형으로 변환한다.

3. 정수형으로 변환한 2개를 더한다. 

4. 더한 결과를 다시 역순 리스트로 변환

 

1번부터 시작하면 다음 코드가 나온다.

 

연결리스트 뒤집기

public ListNode reverseList(ListNode head) {
    // 뒤집은 리스트의 head
    ListNode prev = null;
    ListNode node = head;

    while (node != null) {
        ListNode next = node.next;
        node.next = prev;
        prev = node;
        node = next;
    }

    return prev;
}

 

 

연결리스트를 긴 정밀도 정수형으로 변환

정수형으로 변환할 때 Integer 대신에 BigInteger을 사용한다. 그 이유는 연결리스트가 굉장히 길수가 있기 때문에 이를 Integer으로 선언할 경우 최댓값을 초과할 수 있다. 그래서 BigInteger을 사용한다

 

 

public BigInteger toBigInt(ListNode node) {
    String val = "";
    while (node != null) {
        val += node.val;
        node = node.next;
    }
    return new BigInteger(val);
}

 

 

더한 BigInteger 결과를 역순 연결리스트로 변환

먼저, 문자로 변경한다음 한 글자씩 순회하면서 다시 숫자로 바꾼다. 그다음 숫자를 ListNode를 만들어 역순 연결리스트를 만든다.

 

public ListNode toReversedLinkedList(BigInteger val){
    ListNode prev = null;
    ListNode node = null;

    for(char c : String.valueOf(val).toCharArray()){
        node = new ListNode(Character.getNumericValue(c));
        node.next = prev;
        prev = node;
    }

    return node;
}

 

 

메인 함수

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    // L1, L2 리스트 뒤집기
    ListNode l1reversed = reverseList(l1);
    ListNode l2reversed = reverseList(l2);

    // 더하기 진행
    BigInteger result = toBigInt(l1reversed).add(toBigInt(l2reversed));
    return toReversedLinkedList(result);
}

 

---

 

전략 2. 전가산기 구현

위와 같이 자료형을 일일이 변환하던 풀이는 복잡하고 적어두지 않으면 방향을 잃기 쉽다. 해당 문제를 뒤집지 않고 두 입력값의 합과 자리 올림수의 아이디어를 이용(전가산기 구조를 떠올리면 된다)하여 깔끔하고 오히려 더 쉬운 풀이를 완성할 수 있다.

 

코드에서 먼저 두 입력값의 합을 구한다. 두 입력값의 연산을 수행하고 자릿수가 넘어갈 경우에는 자리 올림수를 설정한다.

 

carry = (sum + carry) / 10; 

10으로 나누었을 때 몫은 자릿수가 증가했다는 의미이므로 carry에 등록한다. 그리고 해당 carry는 다음 덧셈에 사용하게 구현한다.

 

remainder = (sum + carry) % 10;

10으로 나누었을 때 나머지는 노드의 값으로 사용한다. 

 

 

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 임시 노드 선언 => 새롭게 만들어진 리스트의 첫번째 노드를 기억하기 위한 노드이다
    ListNode node = new ListNode(0);

    // 임시 노드를 첫 번째 노드로 선언
    ListNode root = node;

    // 자릿수의 합(sum), 자리올림수(carry), 나머지(remainder)
    int sum, carry = 0, remainder;

    // 모든 연결리스트를 끝까지 순회하고, 자리올림수도 0이 될 때까지 진행
    while (l1 != null || l2 != null || carry != 0) {
        sum = 0;
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }

        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        //자리값 (나머지를 이용) 예를들어 5+8 이면 13인데 3은 자리값. 1은 carry(자리 올림수)
        remainder = (sum + carry) % 10;

        carry = (sum + carry) / 10;
        node.next = new ListNode(remainder);

        //계산할 노드를 다음으로 이동
        node = node.next;
    }

    //아까 첫번째 노드의 임시노드를 가르키는 root에서 다음으로 이동하고 리턴
    return root.next;
}