[파이썬 알고리즘 인터뷰] 두 수의 덧셈

(16) 두 수의 덧셈

★★ Normal

github.com/onlybooks/algorithm-interview

 

[LeetCode]

 

Add Two Numbers - LeetCode

---

1. 나의 풀이

;; 책에 있는 코드 너무 길다.  연결리스트를 뒤집고 연결리스트를 더하고 다시 변환하고.. 엄첨난 양의 코드다.

난 그냥 문자열로 합치고 뒤집은 다음에 더했다.  아래처럼 풀어도 책에 있는 풀이와 속도차이가 없다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        str_l1, str_l2 = '', ''
        
        while l1:
            str_l1 += str(l1.val)
            l1 = l1.next
        while l2:
            str_l2 += str(l2.val)
            l2 = l2.next
        
        sum_val = int(str_l1[::-1]) + int(str_l2[::-1])
        if sum_val == 0:
            return ListNode(val=0)
        else:
            sum_val = str(sum_val)
 
        answer = ListNode(val=sum_val[-1])
        node = answer
        for val in sum_val[-2::-1]:
            node.next = ListNode(val=val)
            node = node.next
            
        return answer

 

---

2. 풀이법

 2-1. 전가산기 구현

..? 갑자기 전가산기?! 

 

아, 두 값을 더해서 나머지가 있으면 다음 계산 때 추가해주는 방식을 이야기하는 것이였다. 

 

onlybooks/algorithm-interview

 

 

자바

자바가... Interger.parseInt의 자리수에 막혀서 위 풀이가 먹히질 않는다.. 

Double.parseDouble을 이용해보긴 했는데 그럼 toString()에서 막힌다. 9.999999991E9 > 그대로 E를 집어넣어버림.. ㅇ0ㅇ

 

/**
 * 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) {
        String str1="", str2="";
        while(l1 != null){
            str1 += String.valueOf(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            str2 += String.valueOf(l2.val);
            l2 = l2.next;
        }
        StringBuffer sb1 = new StringBuffer(str1); 
        String reverseStr1 = sb1.reverse().toString();
        
        StringBuffer sb2 = new StringBuffer(str2); 
        String reverseStr2 = sb2.reverse().toString();
    
        int sum_val = Integer.parseInt(reverseStr1) + Integer.parseInt(reverseStr2);
        
        String str_sum_val = "";
            
        if(sum_val == 0)
            return new ListNode(0);
        else
            str_sum_val = String.valueOf(sum_val);
        
        int firstval = str_sum_val.charAt(str_sum_val.length()-1) - '0';
        System.out.println(firstval);
        ListNode answer = new ListNode(firstval);
        ListNode node = answer;
        
        for (int i = str_sum_val.length()-2 ; 0 <= i ; i--) {
            node.next = new ListNode(str_sum_val.charAt(i) - '0');
            node = node.next;
        
        }
        
        return answer;
    }
}

 

Discussion보니까 다 가산기 방법으로 푸렀닭 🐔

아래 코드가 굉장히 인상적이였다. 

삼항 연산자를 엄첨 자주쓰는것을 보았다.  자바에서는 삼항 연산자가 짱인갑다. 이론은 같다.

My easy JAVA solution - LeetCode Discuss

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