문제
입력으로 두개의 ListNode가 주어졌을때 두개의 합을 반환하는 문제
풀이
두가지 풀이가 존재한다.
첫번째 풀이는 두개의 ListNode의 val값을 추출해서 더한뒤 ListNode로 변환하는 풀이가 존재한다.
예를들어 위 그림과 같은경우 첫번째 ListNode에서 243을 추출, 두번째 ListNode에서 564를 추출하여 두개를 더한뒤, 더한값(708)의 각 자리수를 val로 가지는 ListNode를 만들어 반환한다. 다소 비효율적인 풀이라고 할수있다.두개의 ListNode를 모두 순회하고 ListNode를 생성하는 과정까지 이루어져야하기 때문이다.
두번째 풀이는 동시에 두개의 ListNode를 순회하면서 값을 더하고 그 값을 ListNode로 만드는 방법이다.
l1, l2는 각각 ListNode의 첫번째를 가리킨다.
초기의 올림값은 0이 된다.
res는 결과로써 반환할 ListNode이다. 초기값으로는 0을 부여했다.(결과와 관계없음)
cur은 res를 가리킨다.
l1, l2가 가리키는 값이 모두 없거나 올림값이 0일때까지 아래의 내용을 반복한다.
carry값은 이전 계산에서 만들어진 올림값이다.
carry의 값을 우리가 새롭게 생성할 ListNode의 val값이 되는 n에 저장한다.
l1이 빈 리스트라면 l1.val은 존재하지 않는다. 만약에 l1이 빈 리스트가 아니라면 l1의 값을 n에 저장하고 l1을 l1이 가리키고 있는 다음 ListNode로 이동시킨다.
l2에도 l1과 같은 일을 수행시킨다.
n에는 이제 l1의 값 l2의 값 이전 연산에서 이루어졌던 올림의 값까지 더해져있다. 각 ListNode는 한자리수의 값을 가지므로 n의 값이 9가 넘을 경우, 올림이 일어나야한다. 10으로 나누어 올림값과 다음 ListNode의 값을 각각 만들어낸다. 위 계산을 통해 얻어낸값으로 ListNode를 생성한다. 그리고 그 ListNode(r)는 현재 cur의 다음값으로 지정된다. 이후 cur을 이동시켜 다음 반복에 이용되게 한다. 위 과정을 그림으로 나타내면 다음과 같다.
최종적으로 res는 0->1->5->0->1을 가리키게 되며 결과값으로 res.next를 반환하면 정답임을 알수있다.
이 문제에서 주의해야할점은 반복문을 돌며 노드 생성 과정을 l1, l2이 None값을 그리고 carry값이 0일 때까지 반복해야한다는점이다.
코드
'''
Created by jun on 21/05/02
'''
# 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:
carry = 0
res = cur = ListNode(0)
while l1 or l2 or carry: # l1, l2가 모두 널이면서 carry가 없을때 종료한다.
val1 = 0
if l1:
val1 = l1.val
l1 = l1.next
val2 = 0
if l2:
val2 = l2.val
l2 = l2.next
carry, val = divmod(val1+val2+carry,10)
cur.next = ListNode(val)
cur = cur.next
return res.next
새로 알게된 사실
몫, 나머지 = divmod(연산에 수행되는 값, 나누는값)
