{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 연결 리스트"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 두 수의 덧셈"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"https://leetcode.com/problems/add-two-numbers/"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"역순으로 저장된 연결 리스트의 숫자를 더하라\n",
"\n",
"입력 : \n",
"\n",
"(2 -> 4 -> 3) + (5 -> 6 -> 4)\n",
"\n",
"출력 : \n",
"\n",
"7 -> 0 -> 8\n",
"\n",
"설명 : 342 + 465 = 807"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from typing import List "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"class ListNode:\n",
" def __init__(self, val=0, next=None):\n",
" self.val = val\n",
" self.next = next "
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"def printLinkedList(head: ListNode):\n",
" while head:\n",
" print(head.val)\n",
" head = head.next"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [],
"source": [
"node_3 = ListNode(3)\n",
"node_2 = ListNode(4, node_3)\n",
"node_1 = ListNode(2, node_2)\n",
"\n",
"node_6 = ListNode(4)\n",
"node_5 = ListNode(6, node_6)\n",
"node_4 = ListNode(5, node_5)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:\n",
" num1 = ''\n",
" num2 = ''\n",
" while l1:\n",
" num1 = str(l1.val) + num1\n",
" l1 = l1.next\n",
" \n",
" while l2:\n",
" num2 = str(l2.val) + num2\n",
" l2 = l2.next\n",
" \n",
" s = int(num1) + int(num2)\n",
" \n",
" s_l = list(str(s))\n",
" \n",
" cur = None\n",
" for x in s_l:\n",
" nxt = ListNode(x, cur)\n",
" cur = nxt\n",
" \n",
" return cur"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"7\n",
"0\n",
"8\n"
]
}
],
"source": [
"printLinkedList(addTwoNumbers(node_1, node_4))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\tAccepted\t72 ms\t14.4 MB\tpython3\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 풀이 1. 자료형 변환"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [],
"source": [
"def reverseList(head: ListNode) -> ListNode:\n",
" node, prev = head, None\n",
" \n",
" while node:\n",
" next, node.next = node.next, prev\n",
" prev, node = node, next\n",
" \n",
" return prev"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [],
"source": [
"def toList(node: ListNode) -> ListNode:\n",
" list: List = []\n",
" while node:\n",
" list.append(node.val)\n",
" node = node.next\n",
" return list"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"def toReversedLinkedList(result: str) -> ListNode:\n",
" prev: ListNode = None\n",
" for r in result:\n",
" node = ListNode(r)\n",
" node.next = prev\n",
" prev = node"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [],
"source": [
"def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:\n",
" a = toList(reverseList(l1))\n",
" b = toList(reverseList(l2))\n",
"\n",
" resultStr = int(''.join(str(e) for e in a)) + \\\n",
" int(''.join(str(e) for e in b))\n",
"\n",
" return toReversedLinkedList(str(resultStr))"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"printLinkedList(addTwoNumbers(node_1, node_4))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\tAccepted\t84 ms\t14.4 MB\tpython3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 풀이 2. 전가산기 구현"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:\n",
" root = head = ListNode(0)\n",
" \n",
" carry = 0\n",
" while l1 or l2 or carry:\n",
" sum = 0\n",
" \n",
" if l1:\n",
" sum += l1.val\n",
" l1 = l1.next\n",
" if l2:\n",
" sum += l2.val\n",
" l2 = l2.next\n",
" \n",
" carry, val = divmod(sum + carry, 10)\n",
" head.next = ListNode(val)\n",
" head = head.next\n",
" \n",
" return root.next"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"7\n",
"0\n",
"8\n"
]
}
],
"source": [
"printLinkedList(addTwoNumbers(node_1, node_4))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\tAccepted\t72 ms\t14.3 MB\tpython3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 숫자형 리스트를 단일 값으로 병합하기"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [],
"source": [
"a = [1, 2, 3, 4, 5]"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'12345'"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(str(e) for e in a)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'12345'"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"''.join(map(str, a))"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"import functools"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"12345"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"functools.reduce(lambda x, y: 10 * x + y, a, 0)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [],
"source": [
"from operator import add, mul"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"15"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"functools.reduce(add, a)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"120"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"functools.reduce(mul, a)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.2"
}
},
"nbformat": 4,
"nbformat_minor": 4
}