[자바 알고리즘 인터뷰] 8장 연결 리스트 (4) - 두수의 덧셈

 

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

 

 

 

 

풀이 1) 자료형 변환 

 

- 연결 리스트를 문자열로 이어 붙인 다음에 숫자로 변환하고, 이를 모두 계산한 후 다시 연결 리스트로 바꾸기 

 

1.

 

- 반복 구조로 역순 연결리스트 만들기 

public ListNode reverseList(ListNode head) {
        ListNode prev = null, node = head;

        //노드 끝으로 이동할 때까지 순회
        while(node != null)
        {
            //현재 노드의 다음 노드 미리 지정
            ListNode next = node.next;
            //현재 노드의 다음으로 이전 노드 지정
            node.next = prev;
            //이전 노드는 현재 노드로 지정 
            prev = node;
            //미리 지정했던 다음 노드를 현재 노드로 변경
            node = next;
        }
        //prev는 뒤집힌 연결 리스트의 첫 번째 노드 
        return prev;
    }

 

 

2.

 

- 덧셈 연산을 위해 연결 리스트를 숫자로 변경

- 연결 리스트를 순회하며 한 글자씩 문자열로 만든 다음 이를 숫자로 변경

//연결 리스트를 임의 정밀도 정수형으로 변환
    public BigInteger toBigInt(ListNode node)
    {
        String val="";
        //연결 리스트를 순회하며 한 글자씩 조합
        while(node!=null)
        {
            val += node.val;
            node = node.next;
        }
        //조합한 글자를 임의 정밀도 정수형으로 변환
        return new BigInteger(val);
    }

 

 

3.

 

- 숫자를 다시 연결 리스트로 바꿔주는 함수 

- 일단 문자로 변경한 다음 한 글자씩 순회하며 다시 숫자로 바꿔서 노드를 생성하는 작업 필요 

- 현재 노드의 다음으로 이전 노드를 지정하는 식으로 역순으로 연결 리스트를 만들어서 최종적으로 리턴 

 

//임의 정밀도 정수형을 연결 리스트로 변환
    public ListNode toReversedLinkedList(BigInteger val)
    {
        ListNode prev = null, node = null;
        //정수형을 문자로 바꾼 다음 문자 배열로 전환하여 한 글자씩 순회
        for(char c: String.valueOf(val).toCharArray) {
            //한 글자씩 숫자로 변환하여 노드 지정
            node = new ListNode(Character.getNumericValue(c));
            //최종 결과는 뒤집어야 하므로 현재 노드의 다음으로 이전 노드 지정
            node.next = prev;
            //이전 노드는 현재 노드로 지정
            prev = node;
        }
        return node;
    }

 

 

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, node = head;

        //노드 끝으로 이동할 때까지 순회
        while(node != null)
        {
            //현재 노드의 다음 노드 미리 지정
            ListNode next = node.next;
            //현재 노드의 다음으로 이전 노드 지정
            node.next = prev;
            //이전 노드는 현재 노드로 지정 
            prev = node;
            //미리 지정했던 다음 노드를 현재 노드로 변경
            node = next;
        }
        //prev는 뒤집힌 연결 리스트의 첫 번째 노드 
        return prev;
    }

    //연결 리스트를 임의 정밀도 정수형으로 변환
    public BigInteger toBigInt(ListNode node)
    {
        String val="";
        //연결 리스트를 순회하며 한 글자씩 조합
        while(node!=null)
        {
            val += node.val;
            node = node.next;
        }
        //조합한 글자를 임의 정밀도 정수형으로 변환
        return new BigInteger(val);
    }

    //임의 정밀도 정수형을 연결 리스트로 변환
    public ListNode toReversedLinkedList(BigInteger val)
    {
        ListNode prev = null, 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)
    {
        //2개의 연결 리스트를 뒤집는다.
        ListNode l1Reversed = reverseList(l1);
        ListNode l2Reversed = reverseList(l2);

        //임의 정밀도 정수형으로 변환하여 더하기 연산 진행
        BigInteger result = toBigInt(l1Reversed).add(toBigInt(l2Reversed));
        //결과를 다시 역순 연결 리스트로 변환
        return toReversedLinkedList(result);
    }
}

37밀리초 

 

 

풀이 2) 전가산기 구현 

 

- 논리 회로의 전가산기(Full Adder)와 유사한 형태로 구현 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자:박상길 <책만>

 

- 입력 값 A와 B, 이전의 자리 올림수(Carry in) 이렇게 3가지 입력으로 합(Sum)과 다음 자리 올림수(Carry out) 여부를 결정

-  덧셈 결과에 나머지(Remainder)를 취하고 몫(Quotient)은 자리올림수 형태로 올리는 전가산기 전체적인 구조만 참고해 풀이 

 

- 두 입력값의 합 구하기 

- 전가산기 회로도에서 A,B의 역할과 동일

sum = 0;
//첫 번째 연결 리스트 합산 및 진행
if(l1 != null)
{
   sum+=l1.val;
   l1 = l1.next;
}
//두 번째 연결 리스트 합산 및 진행
if(l2 != null)
{
    sum+=l2.val;
    l2 = l2.next;
}

 

- 두 입력값의 연산을 수행하고 다음과 같이 자릿수가 넘어갈 경우에는 자리올림수를 설정 

- 10으로 나누었을 때 몫은 자릿수가 증가했다는 의미이므로 carry로 사용 

carry = (sum+carry)/10;

 

- 나머지는 노드의 값으로 사용 

- 나머지를 구한 뒤 다음 노드의 값으로 사용 

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

 

- 가산 결과가 두 자릿수가 될 경우 몫은 자리올림수로 설정해 다음번 덧셈에 사용되게 하고 나머지는 값으로 취한다. 

- 이 값을 연결리스트로 만들어주면 된다. 

 

class Solution {
    
    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;
            }

            //노드의 값으로 사용할 나머지 계산
            remainder = (sum+carry)%10;
            //10으로 나누었을 때 몫은 자리수가 증가했다는 의미이므로 자리올림수로 사용
            carry = (sum+carry)/10;
            //나머지는 다음 노드의 값으로 지정
            node.next = new ListNode(remainder);
            //계산할 노드를 다음으로 이동
            node = node.next;
       }

       //첫 번째 노드는 임시 노드이므로 그다음부터 결과로 리턴 
       return root.next;
    }
}

1밀리초